Past exam of the probability, statistics and options I course of the University of Oxford / 2008 / R / 1

Decode the Prüfer code by repeatedly attaching the smallest label absent from the remaining code to its first entry. This produces the successive edges $1-2$, $3-6$, $4-2$, $5-2$, followed by the final edge $2-6$. Thus

Take root one, its children two and three, the children of two to be four and five, and those of three to be six and seven. Its edge set is $\{12,13,24,25,36,37\}$. The root has degree two, vertices two and three have degree three, and the remaining vertices have degree one.

Removing the smallest available leaves in order gives $4,5,2,1,6$, with recorded neighbors $2,2,1,3,3$. Therefore its Prüfer code is

If there are $i$ nonroot interior vertices and $\ell$ leaves, then $1+i+\ell =7$ and the tree degree sum is $2+3i+\ell =12$. Hence $i=2$ and $\ell =4$. Distribute these two nonroot interior vertices among the root's two descendant branches.

Either each branch contains one interior vertex, producing the balanced tree with two cherries, or both are in one branch while the other branch is a leaf. The latter gives a single unbalanced shape, because left and right children are not ordered. Thus there are two unlabelled rooted binary trees. A plane ordering of children would be additional structure not present in the question.

In a Prüfer code, a vertex label occurs exactly its degree minus one times. A rooted binary tree with $2m+1$ vertices has one root of degree two, $m-1$ other interior vertices of degree three, and $m+1$ leaves. Its code of length $2m-1$ therefore has one label occurring once, $m-1$ labels occurring twice, and all other labels absent.

Conversely, these multiplicities force exactly those degrees in the tree decoded from the sequence. The unique once-occurring label is its root. This is the complete characterization.