Cayley公式

固定顶点集为 $\{1,\dots,n\}$,对 $n\ge2$ 定义带标号树 $T$ 的Prüfer序列:反复找到标号最小的叶子,记下其唯一邻居的标号,然后删去该叶子;当只剩下 $2$ 个顶点时停止。这样记录了 $n-2$ 个标号(每删除一次记一个,因为从 $n$ 个顶点开始、停在 $2$ 个),所以每棵带标号树都产生 $\{1,\dots,n\}^{n-2}$ 中的一个序列。

这样的序列恰有 $n^{n-2}$ 个,因为 $n-2$ 个位置中的每一个都可独立取 $n$ 个标号中的任意一个。剩下要证明这个编码是一个双射,使带标号树与这些序列一一对应。

关键事实是:在Prüfer序列中,标号 $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}$ 棵。