木

木からどの辺を取り除いても非連結になり、どの辺を足しても閉路ができる——木はすべてを連結するのにちょうど必要な数の辺を持ち、余りも不足もない。この三つの条件はそれぞれ異なる角度からこの「ちょうど十分な」構造を捉えている。

(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$ は連結である。

$n$ 個の区別可能な点を木の形をしたネットワークに配線する方法が何通りあるかという純粋に組合せ論的な問いに、驚くほど単純な閉じた公式で答えている。これを証明するために使われる符号化のトリック(プリューファー列)は、「木を数える」問題を「列を数える」というずっと易しい問題に変換する。

頂点集合を $\{1,\dots,n\}$ に固定し、$n\ge2$ に対してラベル付き木 $T$ のプリューファー列を定義する:最小ラベルの葉を繰り返し見つけ、その唯一の隣接頂点のラベルを書き留め、その葉を削除する。$2$ 個の頂点が残った時点で止める。これにより $n-2$ 個のラベルが記録される($n$ 個の頂点から始めて $2$ で止めるため、削除一回につき一つ)。よってすべてのラベル付き木は $\{1,\dots,n\}^{n-2}$ 内の列を生成する。

$n-2$ 個の各位置が独立に $n$ 個のラベルのいずれかを取りうるため、このような列はちょうど $n^{n-2}$ 個存在する。あとはこの符号化が全単射であること、すなわちラベル付き木がこれらの列と一対一に対応することを示せばよい。

鍵となる事実は、プリューファー列においてラベル $i$ がちょうど $\deg(i)-1$ 回現れることである:$i$ の隣接頂点が葉として削除されるたびに $i$ が一回書き留められ、$i$ 自身は接続辺が一本を残してすべて失われたときにのみ削除される(書き込みには寄与しない)。特に、列に一度も現れないラベルはちょうど元の葉である。これにより復号が可能になる:列 $(a_1,\dots,a_{n-2})$ が与えられたとき、残っている列の要素としてまだ使われておらず、かつまだ接続されていない最小のラベルを繰り返し取り、それを残っている列の先頭要素に辺で結び、そのラベルを以後の候補から外し、その要素を列から取り除く。$n-2$ 個すべての要素を使い切ったら、残った $2$ 個のラベルを最後の辺で結ぶ。

この復号手順は、残っている頂点数に関する帰納法により、各段階で符号化器が記録したであろう最小ラベルの葉と隣接頂点を正確に特定し、符号化を一段階ずつ厳密に逆転させる。したがって符号化と復号は互いに逆写像であり、$n$ 個の頂点上のラベル付き木と $\{1,\dots,n\}^{n-2}$ 内の列との間の全単射が得られる。そのような列が $n^{n-2}$ 個あるので、$n$ 個の頂点上のラベル付き木もちょうど $n^{n-2}$ 個存在する。