ケイリーの公式
n個の点で構成されるラベル付きの木の集合と、記号列「{a1,a2, ..., an-2}」の集合を、1対1で対応させる(全単射)ことを考える。ただし、「ai」は整数であり、「1≦ai≦n」とする。
「1≦ai≦n」(つまり、記号「ai」は1からnまでの値を取りうる)であるから、記号列「{a1, a2, ..., an-2}」の個数は、全部で「n」個あると言える。なので、もしn個の点で構成される木の集合と、記号列「{a1,a2, ..., an-2}」の集合を、1対1で対応させることができたなら、n 個のラベル付き頂点を持つ木の個数が「n」個であるということが直ちに言える。「n=1」または「n=2」の時は自明であるので、「n≧3」の時について考えよう。
端点のラベルで最小のものをb1とし、b1に隣接している点のラベルをa1とする。この時、点b1とその接続辺を除去すると、「n-1」個の点で構成されるラベル付きの木が得られる。次に、この新しい木の端点で最小のラベルをb2とし、点b2に隣接している点のラベルをa2とし、点b2とその接続辺を除去する。このように、端点と隣接辺のセットを次々に除去していき、2つの点になるまで続けていく。