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

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$.