木の同値な特徴づけ

(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$ とその唯一の接続辺を取り除くと、$n-1$ 個の頂点からなるグラフ $T'$ が残り、これは依然連結($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$ は連結である。