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.ネシェトリル 『離散数学への招待』
