求证：树T的顶点v在Prüfer编码中出现次数为deg(v)-1

你的思路完全切中要点，而且可以非常简洁地完成证明：

• 对于初始状态是叶子的顶点v（deg(v)=1），它会被直接移除且不会出现在编码中，恰好对应deg(v)-1=0；
• 当v有邻接叶子被移除时，每移除一个这样的叶子，v就会被加入编码一次，直到v自己变成叶子（此时它的度数已降至1，不会再被加入编码）；
• 最后剩下的两个顶点都不会进入编码，它们此时度数均为1，同样满足出现次数等于deg(v)-1。

本质上，Prüfer编码的生成过程就是不断“消耗”顶点的邻接叶子，每个顶点v被加入编码的次数，恰好等于它需要丢掉的叶子总数——也就是初始度数减去最后保留的1，即deg(v)-1。

内容的提问来源于stack exchange，提问作者Fats