Cayleyの定理 (全域木の総数)1. (次数列による方法)

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$ からなるグラフで木 (閉路をもたないグラフ) であるようなもののこと．

$K_3$ の全域木．全部で 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.ネシェトリル『離散数学への招待』

数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

Cayleyの定理 (全域木の総数)1. (次数列による方法)