ケイリーの公式の証明：行列木定理を用いた別アプローチ

ケイリーの公式は、ラベル付き頂点 n 個からなる完全グラフにおける全ての木（生成木）の数が nⁿ⁻² であることを示す、美しい定理です。この記事では、ダブルカウント以外の方法として、行列木定理（Matrix-Tree Theorem）を用いた証明をわかりやすく紹介します。

ケイリーの公式とは

ケイリーの公式は、次のように表されます。

n 頂点からなるラベル付き完全グラフ K_n に含まれる生成木（スパニングツリー）の数は nⁿ⁻² 本である。

この公式は、ネットワーク理論やアルゴリズム、分子構造の計算など、さまざまな分野で応用されています。

行列木定理とは、任意のグラフに対し、隣接関係を表すラプラシアン行列のある小行列式（cofactor）を使って、そのグラフのスパニングツリーの数を求める方法です。

グラフ G のラプラシアン行列 L を定義し、L の任意の 1 行・1 列を削除して得られる小行列の行列式（determinant）が、G のスパニングツリーの総数になります。

完全グラフ K_n では、各頂点は n−1 個の頂点と接続しています。したがって、ラプラシアン行列 L は次のような構造になります。

L_ij	値
i = j	n − 1
i ≠ j	−1

このような行列は「センター化された全1行列」と呼ばれ、固有値解析がしやすい形式です。

L の任意の 1 行・1 列を削除した小行列は、(n−1)×(n−1) の行列になります。この行列の固有値は。

削除により 0 の固有値が除かれるため、残った行列の行列式は nⁿ⁻² になります。これにより、K_n のスパニングツリーの総数がケイリーの公式 nⁿ⁻² に一致することが示されます。

ダブルカウンティングや Prüfer コードを使った証明も存在しますが、行列木定理は代数的なアプローチであり、構造を深く理解したい方にとって非常に有用です。また、任意のグラフに拡張可能な点も強みです。

たとえば Prüfer コードでは、木構造から一意のコード列を生成し、その逆も可能であることを示すことで nⁿ⁻² 通りの対応を構築します。こちらは組合せ的アプローチです。

ケイリーの公式は、複数の証明方法が存在する数学的にも魅力的な定理です。この記事では、ダブルカウントではなく、行列木定理を用いて代数的に公式を導出しました。少し高度な線形代数の知識は必要ですが、グラフ理論の理解を一層深める助けになるはずです。

他のアプローチと併せて学ぶことで、ケイリーの公式の本質にさらに近づけるでしょう。