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

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.