Prüfer 编码

叶子只有一条边，所以删去它时记录邻点已经保存了它的全部连接信息。表面上似乎还要记录“删的是哪个叶子”，但最小标号约定使这部分信息可以从剩余编码恢复。

若标号 $v$ 在原树中的度数是 $d_v$，它在编码中恰出现 $d_v-1$ 次。与它相连的边中，除最后保留或随它自身删除的一条外，其余每条都会在删除邻叶时记录一次 $v$。因此当前编码中未出现、且还没有被删除的标号正是当前叶子。

逆过程如何维持正确性 ​

给定序列 $p_1,\dots ,p_{n-2}$，先令每个顶点的待分配度数等于“出现次数加一”。处理 $p_i$ 时，从仍在使用的标号中取最小的度数一顶点 $u$，加入边 $u{p}_i$，删除 $u$，并把 $p_i$ 的待分配度数减一。最后把剩余两个顶点连接。

每步都有可选叶子：若当前还剩 $m$ 个标号，剩余编码长 $m-2$，至少两个标号没有出现。所选 $u$ 不会等于首项 $p_i$，因为首项确实出现在剩余编码中。每次接上的是一个随后永久删除的新叶子，逆着看这个过程便是在一条边上逐个添叶，所以产物始终连通且无圈。

对边集 $\{12,23,24,45\}$，这里 $12$ 表示无向边 $\{1,2\}$，编码和解码可逐步对照：

编码为 $(2,2,4)$，最后留下边 $45$。解码第一步中未出现的标号为 $1,3,5$，取 $1$ 接到 $2$；删去一个 $2$ 后取 $3$ 接到 $2$；再取 $2$ 接到 $4$；最后连接 $4,5$，恰恢复原边集。

标号 $2$ 出现两次，所以度数是三；$4$ 出现一次，所以度数是二；其余标号均为叶子。星形树的中心标号会占满全部 $n-2$ 个位置。

当 $n=2$ 时编码为空，但仍唯一确定那条边，因为顶点集已知。$n=1$ 需要单独约定，不能生成长度 $-1$ 的序列。解码必须排除已经删除的标号，否则“当前未出现”会反复选中旧叶子。

任意删叶次序仍能得到一串邻点，但没有统一的确定规则时，这串邻点未必能唯一恢复删除次序。编码依赖标号；把两棵同构树重新编号，通常会改变编码，所以它不能直接对无标号同构类型去重。

双射配合乘法原理理路乘法原理Product rule · Multiplication principle分阶段且每阶段选择数固定时，总数等于各阶段选择数之积。给出Cayley 公式理路Cayley 树计数公式Cayley's formula顶点集固定为 $[n]$ 的标号树恰有 $n^{n-2}$ 棵。 $n^{n-2}$。给定度数 $d_1,\dots ,d_n\ge 1$ 且和为 $2n-2$ 时，各标号的出现次数已经固定为 $d_i-1$，故对应树数由多项式系数理路多项式系数Multinomial coefficient把 n 个可区分对象分入若干有标号组时的计数系数 n!/(n1!⋯nk!)。给出：

独立均匀生成 $n-2$ 个 $[n]$ 中的标号，再解码，会均匀生成标号树。这一结论依赖双射，而非“编码看起来随机”。无标号树不因此均匀，因为不同同构类型拥有不同数量的标号版本。

删除叶子后仍为树的事实由树的等价刻画理路树的等价刻画Characterizations of trees非空有限简单无向图是树，当且仅当它具有唯一简单路径，或连通且恰有 n−1 条边；极小连通与极大无圈也给出等价刻画。保证；它也是编码能够一路进行到两个顶点的结构依据。