Ｋ_nの全域木の数の証明

質問

Ｋ_nはn点からなるグラフ（図形）で、ある任意の点は自分自身以外の点と辺で結ばれています。つまり各辺の次数がn-1のグラフです。

このグラフの全域木の数は一般的にn^(n-2)個であることが知られているそうなのですが、どう証明すればいいでしょうか。

全域木とは、全ての点を通る「木」のことです。つまり全ての点と点を結びつけつつも閉路が存在しないようなグラフのことをいいます。

どなたか分かる方、よろしくお願いします。

回答No.2

graphaffine · ベストアンサー

Cayleyの公式の話ですね。

証明は次の本を見て下さい

１　グラフ理論入門　　サイエンス社発行
　N．ハーツフィールド G．リンゲル 著
　早稲田大学 教授 鈴木晋一 訳
　　「５章２節　ケーリーの全域木公式」参照
２　数え上げの手法　　東海大学出版会発行
　　L.ロバース　著
　　成嶋弘、土屋守正　訳
　　「４章１節　Cayleyの公式と木の数え上げ」参照

回答No.1

korochin

直接答えとは関係ないですけど、
>つまり各辺の次数がn-1のグラフです。
は「各点」ではないですか？
次数とは、ひとつの点にn-1本の辺があるということですよね？

お礼

すいません。おっしゃるとおりです＾＾；