= Solution
The sum of degrees is twice the number of <edges>, so
$$
l+r(n-l)=2(n-1).
$$
For $r\ge2$ this gives
$$
\boxed{n-l=\frac{n-2}{r-1},\qquad l=n-\frac{n-2}{r-1}=\frac{n(r-2)+2}{r-1}.}
$$
Necessity 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 <vertex degree>[degree] $r$ at the chosen labels and <vertex degree>[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\ge2$. If $r=1$, all <vertices> would have <vertex degree>[degree] one, and the only <connected> <tree> with $n\ge2$ is the two-<vertex> <edge>. This separate case is not expressed by division by $r-1$.
Back to article page
