公式証明済み

ラベル付き木に対するケイリーの公式

内容

任意の整数 $n \ge 1$ に対し、ラベル付き $n$ 頂点 $\{1,\dots,n\}$ 上の木の個数は $n^{n-2}$ である（ $n=1$ のときは $1^{-1}=1$ とする）。

なぜ正しいのか?

$n$ 頂点の任意のラベル付き木は、最も小さい番号の葉を取り除いてその隣接頂点を記録する操作を繰り返すことで、長さ $n-2$ の頂点ラベル列（プリューファー列）へと一意に符号化できる。逆に $\{1,\dots,n\}$ からなる長さ $n-2$ の任意の列は一意な木に復号されるため、木の総数は $n^{n-2}$ となる。

証明の概略

$\{1,\dots,n\}$ 上のラベル付き木と $\{1,\dots,n\}^{n-2}$ の列との間のプリューファー全単射を構成する： $n-2$ 回の各段階で最小ラベルの葉を削除し、その唯一の隣接頂点のラベルを列の末尾に付け加えると、最後に一本の辺が残る。頂点 $v$ はプリューファー列にちょうど $\deg(v)-1$ 回現れることに注意すると、元の木の葉は列に現れないラベルとして特定できるため、各段階は一意に逆転可能であり、全単射が成り立つ。

この定理を使うトピック

木

参考文献

Arthur Cayley (1889). A theorem on trees