Prüfer 编码

编码反复删除当前标号最小的叶子，并记录它的邻点；“最小”只用于让编码确定，树结构则保证始终有叶子可删。序列中某标号每出现一次，就表示它在最后保留的那条关联之外还失去一片叶边，所以出现次数等于度数减一。解码时最小未出现标号正是下一片叶子。

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

树边 $\{12,23,24,45\}$ 上，先删叶 $1$ 记录 $2$，再删叶 $3$ 记录 $2$，再删叶 $2$ 记录 $4$，得到 Prüfer 序列 $(2,2,4)$。其中标号 $2$ 出现两次，原度数为三；$4$ 出现一次，原度数为二。编码只适用于顶点有互异标号的树；对无标号树，不同标号编码可能落在同一同构类型。

标号树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。与长度 $n-2$ 的序列公理库序列Sequence以自然数为定义域的函数。建立双射，从而证明Cayley 公式公理库Cayley 树计数公式Cayley's formula顶点集固定为 $[n]$ 的标号树恰有 $n^{n-2}$ 棵。。出现次数还能计数指定度数序列的树，并支持随机均匀生成标号树。树的无圈连通性公理库树的等价刻画Characterizations of trees有限简单无向图是树，当且仅当它具有唯一简单路径、恰有 n−1 条边，或处在连通与无圈的极值边界。保证删除叶子后仍是树，是编码与解码始终可继续的结构基础。