0

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?

Matti P.
  • 6,012
ThisIsHard
  • 1

1 Answers1

0

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

Brian M. Scott
  • 616,228