= Prüfer degree formula
{c}
{title2=$\deg_T(v)=1+\#\{i:p_i=v\}$}
For a <labelled tree> with $n\geq2$ <vertices>, the <vertex degree> of label $v$ is one plus the number of occurrences of $v$ in its <Prüfer sequence>:
$$
\deg_T(v)=1+\#\{i:p_i=v\}.
$$
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. https://www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf[Columbia University, Graph Theory Lecture 4, Proposition 7.1: degree equals occurrences plus one]{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)$.
Back to article page
