1889年、ケイリーはｎ個の頂点をもつラベル付きの木の数t(n)を決定する問題に取り組んだ。

この問題は非常に簡単な答えをもつ。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ケイリーの定理

ｎ個の頂点をもつラベル付きの木の数はt(n)＝ｎ^(n-2)である。

頂点数3のベル付きの木は3個ある。

頂点数4のベル付きの木は16個ある。

頂点数5のベル付きの木は125個ある。

この定理は完全グラフＫnがｎ^(n-2)個のラベル付き全域木をもつことを主張している。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】非同型な全域木

ラベル付きは同型なグラフを同一視しないことを意味している。

頂点数3のベル付きの木は3個ある。→頂点数3の非同型な全域木は1個ある（Ｖ字型＝3！/2！＝3個）

頂点数4のベル付きの木は16個ある。→頂点数4の非同型な全域木は2個ある

（Ｎ字型＝4！/2！＝12個、Ｔ字型＝4！/3！＝4個）

頂点数5のベル付きの木は125ある。→頂点数5の非同型な全域木は3個ある

（Ｘ字型＝5！/4！＝5個、Ｗ字型＝5！/2！＝60個、Ｙ字型＝5！/2！＝60個）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝