ケイリーの公式

頂点集合を $\{1,\dots,n\}$ に固定し、$n\ge2$ に対してラベル付き木 $T$ のプリューファー列を定義する:最小ラベルの葉を繰り返し見つけ、その唯一の隣接頂点のラベルを書き留め、その葉を削除する。$2$ 個の頂点が残った時点で止める。これにより $n-2$ 個のラベルが記録される($n$ 個の頂点から始めて $2$ で止めるため、削除一回につき一つ)。よってすべてのラベル付き木は $\{1,\dots,n\}^{n-2}$ 内の列を生成する。

$n-2$ 個の各位置が独立に $n$ 個のラベルのいずれかを取りうるため、このような列はちょうど $n^{n-2}$ 個存在する。あとはこの符号化が全単射であること、すなわちラベル付き木がこれらの列と一対一に対応することを示せばよい。

鍵となる事実は、プリューファー列においてラベル $i$ がちょうど $\deg(i)-1$ 回現れることである:$i$ の隣接頂点が葉として削除されるたびに $i$ が一回書き留められ、$i$ 自身は接続辺が一本を残してすべて失われたときにのみ削除される(書き込みには寄与しない)。特に、列に一度も現れないラベルはちょうど元の葉である。これにより復号が可能になる:列 $(a_1,\dots,a_{n-2})$ が与えられたとき、残っている列の要素としてまだ使われておらず、かつまだ接続されていない最小のラベルを繰り返し取り、それを残っている列の先頭要素に辺で結び、そのラベルを以後の候補から外し、その要素を列から取り除く。$n-2$ 個すべての要素を使い切ったら、残った $2$ 個のラベルを最後の辺で結ぶ。

この復号手順は、残っている頂点数に関する帰納法により、各段階で符号化器が記録したであろう最小ラベルの葉と隣接頂点を正確に特定し、符号化を一段階ずつ厳密に逆転させる。したがって符号化と復号は互いに逆写像であり、$n$ 個の頂点上のラベル付き木と $\{1,\dots,n\}^{n-2}$ 内の列との間の全単射が得られる。そのような列が $n^{n-2}$ 個あるので、$n$ 個の頂点上のラベル付き木もちょうど $n^{n-2}$ 個存在する。