Leaves in (1,3)-tree
Task number: 4216
How many at most and at least leaves can a tree have on \(n\ge 2\) vertices that has degrees only 1 and 3?
Solution
Let us denote by \(l\) the number of leaves and by \(v\) the number of inner vertices of degree 3.
Directly, we count all edges and vertices:
\( | V_G | = l + v \),
\( 2 | E_G | = l + 3v \) (parity principle).
Substituting into \( | V_G | = | E_G | +1 \) we have \( l + v = \frac12 (l + 3v) +1 \), from which we get \( l = v +2 \).
Alternatively by induction according to the number of internal vertices.
For \( v = 0 \), \( l = 2 \) it is the tree \( K_2 \) and the statement holds.
Take any vertex of degree three and divide it into three leaves. This creates three trees that satisfy the induction hypothesis. For \( i = 1{,}2,3 \) let us denote \( l_i \) and \( v_i \) the numbers of leaves and inner vertices in the \( i \)-th tree.
It holds: \( v = v_1 + v_2 + v_3 + 1 = (l_1-2) + (l_2-2) + (l_3-2) + 1 = l_1 + l_2 + l_3-5 = l-2 \) .
The first and the last equations correspond to the situation where three leaves are formed from one inner vertex by splitting.
Answer
The tree must have an even number of vertices of which \(\tfrac{n}2+1\) are always leaves and \(\tfrac{n}2-1\) are inner vertices.
