树的等价刻画

我们证明 (i) 连通且无环 $\implies$ (ii) 连通且有 $n-1$ 条边 $\implies$ (iii) 无环且有 $n-1$ 条边 $\implies$ (i),从而把三者串成一个环。

**(i)$\implies$(ii)**,对 $n$ 归纳。基础情形 $n=1$ 显然:单个顶点有 $0 = n-1$ 条边。归纳步骤:取一个 $n\ge2$ 个顶点的连通无环图 $T$。由于 $T$ 有限且无环,它必含一个叶子 $v$(度为 $1$ 的顶点):否则每个顶点的度都 $\ge 2$,从任意起点出发沿边前进且不立即折返,最终必会重访某个顶点,从而产生环。删去 $v$ 及其唯一关联边,剩下的图 $T'$ 有 $n-1$ 个顶点,依然连通(没有其他顶点依赖 $v$ 来保持连通)且依然无环(无环图的子图仍无环)。由归纳假设,$T'$ 有 $(n-1)-1$ 条边,故 $T$ 有 $(n-1)-1+1 = n-1$ 条边。

**(ii)$\implies$(iii)**。设 $T$ 连通且有 $n-1$ 条边。若 $T$ 含有一个环,删去该环上的一条边后图仍连通(被删边的两端点仍由环的其余部分相连),这就得到一个在 $n$ 个顶点上只有 $n-2$ 条边的连通图。但任何 $n$ 个顶点上的连通图都至少需要 $n-1$ 条边(除第一个顶点外,每个新顶点都至少需要一条新边才能到达),所以 $n-2$ 条边不可能让 $n$ 个顶点连通——矛盾。故 $T$ 不含环,即无环。

**(iii)$\implies$(i)**。设 $T$ 无环且有 $n-1$ 条边,并设其有 $c$ 个连通分量。每个分量本身连通且无环,于是对每个分量分别应用已证明的 (i)$\implies$(ii) 方向,一个有 $n_i$ 个顶点的分量就有 $n_i - 1$ 条边。对所有分量求和,总边数为 $\sum_i (n_i - 1) = n - c$。已知总数为 $n-1$,故 $n - c = n - 1$,于是 $c=1$:$T$ 连通。