 Prüfer degree formula

For a labelled tree with $n\ge 2$ vertices, the vertex degree of label $v$ is one plus the number of occurrences of $v$ in its Prüfer sequence:Each recording of $v$ corresponds to an incident edge removed when a neighbouring leaf of a graph is deleted. Exactly one incident edge remains when $v$ itself is deleted, or when it belongs to the final pair. In particular, $v$ is a leaf of a graph exactly when it never occurs in the Prüfer sequence. The same reasoning applies to each remaining tree and its remaining code. ^[ref]

For $p=(1,3,3,5)$, the occurrence counts in label order are $(1,0,2,0,1,0)$, giving the degree sequence $(2,1,3,1,2,1)$. Its sum is $10=2(6-1)$, as required by the degree-sum formula. More generally, summing the occurrence counts gives $n-2$, so summing the vertex degrees gives $n+(n-2)=2(n-1)$.