求证：无环图边数k = n - q（n为顶点数，q为连通分量数）

嘿，这个问题其实拆解开来就很好理解啦，咱们分两步走，先搞定连通的无环图（也就是树）的情况，再拓展到多连通分量的场景：

第一步：证明连通无环图（树）的边数 = 顶点数 - 1 #

咱们用数学归纳法来证最直观：

• 基础情况：当顶点数n=1时，图里没有边，1-1=0，完全符合；当n=2时，只能有1条边，2-1=1，也成立。
• 归纳假设：假设所有有m个顶点的连通无环图，边数都是m-1。
• 归纳步骤：现在看一个有m+1个顶点的连通无环图。随便挑一条边删掉，因为图是连通且无环的，删掉这条边后，图会分成两个互不连通的无环子图（两个小的树）。设这两个子图的顶点数分别是a和b，显然a+b = m+1。根据归纳假设，两个子图的边数分别是a-1和b-1，加起来就是(a-1)+(b-1) = a+b-2 = (m+1)-2 = m-1。再把刚才删掉的那条边加回去，总边数就是m-1+1 = m = (m+1)-1，完美符合n-1的结论。归纳成立。

第二步：推广到有q个连通分量的无环图 #

现在你的无环图有q个连通分量，每个分量本身都是连通且无环的——也就是咱们刚才证明的树。
设第i个连通分量的顶点数是n_i，边数是k_i，根据第一步的结论，每个分量都满足k_i = n_i - 1。
把所有分量的边数加起来：
总边数k = k₁ + k₂ + ... + k_q = (n₁-1) + (n₂-1) + ... + (n_q-1)
把括号展开，就是(n₁ + n₂ + ... + n_q) - q
而所有分量的顶点数之和就是整个图的总顶点数n，所以代入后得到：
k = n - q
这就正好是你要证明的结论啦！

补充一句：这里的“可导出无环图”其实就是森林（无环图），不管边是不是从原图导出的，只要图本身无环，这个公式就成立——因为导出只是限定了边的来源，不改变无环和连通分量的性质。

内容的提问来源于stack exchange，提问作者TheWanderer