形式陈述

对顶点集 $[n]$ 上的树，反复删除当前标号最小的叶节点，并记录它的唯一邻点，直至剩余两个顶点，得到长度 $n-2$ 的 Prüfer 序列。 逆过程维护各标号在剩余序列中的出现次数，每一步把当前最小的零出现次数标号连接到序列首项，再删除该首项；最后连接剩余两个标号。两过程互逆。

直觉

序列记录每次剪掉叶子时树剩余部分中的连接点；树的分叉程度转化为标号在序列中的重复次数。

例子与边界

星图中心在 Prüfer 序列中出现 $n-2$ 次。顶点 $v$ 的度数等于它在编码中的出现次数加一。编码依赖顶点标号，不直接计数无标号树。

推论与应用

它给出 Cayley 公式的透明双射证明，也用于随机标号树生成与给定度数序列的树计数。

参考资料

• Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science (2018/2024), Prüfer codes.
• Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd ed. (2011), labeled trees.