Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / R / R2

Encode a labelled tree by repeatedly deleting its smallest-labelled leaf of a graph and recording its neighbor, stopping when two vertices remain. This produces a sequence of length $n-2$ with entries in $\{1,\dots ,n\}$.

Conversely, given such a sequence, at each step choose the smallest unused label not occurring in the remaining sequence, join it to the first sequence entry, delete that chosen label and the first entry, and continue. Finally join the two labels left over. A label outside the remaining sequence always exists because two more labels than entries remain. The process never uses a previously deleted label as a sequence entry. Each step attaches a new leaf of a graph to the eventual remaining graph, so backward induction shows that the result is connected and acyclic, hence a tree.

In a tree encoding, a vertex occurs once for every incident edge except the edge by which it is eventually removed, or the final surviving edge. Thus its number of occurrences is its degree minus one. The labels absent from the current remaining sequence are exactly the current leaves of a graph. Both procedures therefore choose the same smallest leaf of a graph and edge at every stage. They are inverse maps, proving the claimed bijection, including the empty sequence when $n=2$.

There are ten labels. The successive deleted leaves of a graph are $3,4,5,1,6,7,2,9$, paired with the respective entries $1,1,1,2,2,2,8,8$. The final two labels are $8,10$. Thus the tree has edge setHere $ij$ denotes the unordered edge $\{i,j\}$; the last edge is written with a separator to distinguish label ten. Equivalently its adjacency lists are $1:\{2,3,4,5\}$, $2:\{1,6,7,8\}$, $8:\{2,9,10\}$, with all other vertices leaves of a graph. These lists make the constructed tree unambiguous.

A label appears in the code exactly its degree minus one times, as proved in (i). It is a leaf of a graph exactly when it never appears. ThereforeFor example the code in (ii) uses three distinct labels, so its ten-vertex tree has seven leaves of a graph.

For $n=1$ there are no edges. Every finite tree with at least two vertices has a leaf of a graph: an endpoint of a longest simple path cannot have another neighbor, since that would either create a cycle or extend the path. Delete that leaf of a graph and its sole edge. The remaining graph is still a tree, so induction gives $n-2$ remaining edges and $\boxed{n-1}$ original edges. Alternatively the decoding construction in (i) inserts exactly $n-2$ edges and then the final edge.

The sum of degrees is twice the number of edges, soFor $r\ge 2$ this givesNecessity of the divisibility condition follows. Conversely, when $r-1\mid n-2$, choose $k=(n-2)/(r-1)$ internal labels and form a Prüfer sequence in which each of them appears exactly $r-1$ times. Its length is $n-2$; all other labels are absent. The decoded tree has degree $r$ at the chosen labels and degree one elsewhere. Thus the divisibility condition is sufficient, with the displayed leaf of a graph count. For $n=2$ the code is empty and the sole edge works, with no internal vertices.

The division assumes $r\ge 2$. If $r=1$, all vertices would have degree one, and the only connected tree with $n\ge 2$ is the two-vertex edge. This separate case is not expressed by division by $r-1$.

First choose the $l$ absent labels, which will be the leaves of a graph, in $\left(\genfrac{}{}{0ex}{}{n}{l}\right)$ ways. Every other label must occur exactly $r-1$ times in the Prüfer sequence. There are $n-l$ such labels and their total multiplicity is $n-2$ by (a). The number of orderings of this multiset is $(n-2)!/((r-1)!{)}^{n-l}$. The bijection in (i) turns each ordering into one distinct labelled tree and exhausts all possibilities. ThereforeThe formula is used with the feasible integer parameters from (a), and gives one for the two-vertex edge with no internal labels.