A tree with degree 7 has
- 7 nodes with degree 2,
- 6 nodes with degree 3,
- 5 nodes with degree 4,
- 4 nodes with degree 5,
- 3 nodes with degree 6, and
- 2 nodes with degree 7.
How many leaf nodes does the tree have? a) 35 b) 28 c) 77 d) 78
By doing it the brute way (just counting), I found that there supposed to be 84 leaf nodes. What am I missing here?
The correct answer is $52$. Let $n$ be the number of leaves and $e$ the number of edges. There are $\sum_{k=2}^7k=27$ non-leaf nodes, so $e=(27+n)-1=26+n$. On the other hand, if we sum the degrees of the the $27+n$ nodes we get $104+n$, so $2e=104+n$. Thus, $2(26+n)=104+n$, and $n=52$.
Alternatively, we could use the formula from this question: we have all of the information needed to calculate the righthand side, and we find that $v_1=52$.