Cayley の定理
この記事では,グラフの全域木の個数に関する Cayley の定理を紹介します.
定理 (Cayley)
任意の自然数 \(n\geq 2\) に対して,頂点数が \(n\) である完全グラフ \(K_n\) の全域木の総数は
\begin{align*}
T(K_n) = n^{n-2}
\end{align*}
一般のグラフ \(G\) の全域木の総数を \(T(G)\) の記号で表すこととします.
ここでは,4 通りの証明を紹介していきます(長くなるので別々の記事に分けます).4 つ目のラプラシアン行列を用いる方法では完全グラフ \(K_n\) に限らず一般のグラフの全域木の総数を求めることができます.
言葉の説明
頂点数が \(n\) の完全グラフ \(K_n\) とは,
\(n\) 個の頂点のうち任意の 2 点の間に枝が存在するようなグラフのこと.

3頂点の完全グラフ \(K_3\)
グラフ \(G=(V, E)\) の全域木とは,
グラフ \(G\) のすべての頂点と \(E\) の部分集合 \(T\) からなるグラフで木 (閉路をもたないグラフ) であるようなもののこと.

K3 の全域木.全部で 3 種類ある.
証明
1. 次数列による方法
命題1.
\(n\geq 2\) とする.\(d_1, d_2, \ldots, d_n\) を和が \(2n-2\) である正の整数の列とする.このとき,頂点 \(i\) \((i=1, 2, \ldots, n)\) の次数が \(\deg{i}=d_i\) であるような \(K_n\) の全域木の総数は
\begin{align*}
\dfrac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}.
\end{align*}
頂点の次数とは,その頂点から出ている枝の数のことです.
\(n\) 頂点の木では,枝の総数は \(n-1\) 本なので,すべての頂点の次数の和はその 2 倍である \(2n-2\) になります.
命題1. の証明
この命題は \(n\) に関する帰納法で証明します.
まず \(n=2\) の場合は \(d_1=d_2=1\) であり,全域木は 1 つしかない (\(K_2\)自身のみ) ので,成り立ちます.
そこで,\(n>2\) の場合を考えます.
\[d_1+d_2+\cdots+d_n=2n-2<2n\]
なので,少なくとも 1 つの頂点においてその次数が 1 です.
そこで,\(d_n=1\) とします.
(頂点の番号付け \(1, 2, \ldots, n\) は自由に決めてよいので,次数が 1 の頂点と頂点 \(n\) を入れ替えると考える.)
各頂点 \(i\) の次数が \(d_i\) であるような \(K_n\) の全域木の全体の集合を \(\mathcal{T}\) とします.
また,頂点 \(n\) はほかの 1 つの頂点とのみ隣接するので,\(\mathcal{T}\) のうち頂点 \(n\) が頂点 \(j\) と隣接しているような全域木を \(\mathcal{T}_j\) とすると,
\begin{align}
\mathcal{T} = \mathcal{T}_1\sqcup\mathcal{T}_2\sqcup\cdots\sqcup\mathcal{T}_{n-1} \tag{1}
\end{align}
と書けます.
(記号 \(\sqcup\) は,\(\mathcal{T}_1, \ldots, \mathcal{T}_{n-1}\) に重複がないような和集合であるという意味です).
さて,\(\mathcal{T}_j\) に含まれる木から頂点 \(n\) と,頂点 \(n\) に接続する枝を取り除いたものは \(K_{n-1}\) の全域木になっており,その次数列は
\[d_1, d_2, \ldots, d_{j-1}, d_j-1, d_{j+1}, \ldots, d_{n-1}\]
となります.
この次数列をもつ \(K_{n-1}\) の全域木全体を \(\mathcal{T}^\prime_j\) とすると,\(\mathcal{T}_j\) の木と \(\mathcal{T}^\prime_j\) の木には 1 対 1 対応が得られたことになるので,帰納法の仮定から,
\begin{align*}
|\mathcal{T}_j| &= |\mathcal{T}^\prime_j|\\
&= \dfrac{(n-3)!}{(d_1-1)!(d_2-1)!\cdots(d_{j-1}-1)!(d_j-2)!(d_{j+1}-1)!\cdots(d_{n-1}-1)!}\\
&= \dfrac{(n-3)!(d_j-1)}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}
\end{align*}
よって,(1)式から,次数列が \(d_1, d_2, \ldots, d_n(=1)\) である全域木の総数は,
\begin{align*}
|\mathcal{T}| &= \sum_{j=1}^{n-1}|\mathcal{T}_j|\\
&= \sum_{j=1}^{n-1} \dfrac{(n-3)!(d_j-1)}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}\\
&= \dfrac{(n-3)!}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}\sum_{j=1}^{n-1} (d_j-1)\\
&= \dfrac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_{n-1}-1)!}
\end{align*}
ここで,\(d_1+d_2+\cdots+d_{n-1}=2n-2-d_n=2n-3\) であることを用いています.
分母に \((d_n-1)! = 1\) を掛ければ命題 1. の式が得られます.
Cayley の定理の証明
あとは命題1. の右辺をすべての次数列について和を取ればよく,
\begin{align*}
T(K_n) &= \sum_{\substack{d_1, d_2, \ldots, d_n\geqq 1\\
d_1+d_2+\cdots+d_n=2n-2}} \dfrac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}\\
&= \sum_{\substack{k_1, k_2, \ldots, k_n\geqq 0\\k_1+k_2+\cdots+k_n=n-2}} \dfrac{(n-2)!}{k_1!k_2!\cdots k_n!}\\
&= n^{n-2}
\end{align*}
となります.
参考:J.マトウシェク/J.ネシェトリル 『離散数学への招待』