How many inner vertices does this tree have?

Question

A tree with 125 vertices has half the inner vertices with degree 3 and other half with degree 2. How many inner vertices does it have? I know all the necessary definitions, but I just can't figure out how to get the answer.

Answer 1

There are 125 vertices. It is a tree so there are 124 edges. From the question, let $k$ be the number of vertices with degree 2. We also have $k$ vertices with degree 3. We are left with $125 -2 k $ vertices with degree 1 (terminal vertices).

Adding up all the degrees gives us twice the number of edges so $ 2k + 3k + 1\times (125 - 2 k) = 2 \times 124 $ giving $k = 41$, so in total there are 82 inner vertices.

Answer 2

HINT

1. Let $n_k$ be the number of vertices of degree $k$ in the tree. Then, $n_2=n_3$ and $n_4=n_5=\ldots = 0$.
2. You know $|V| = 125$, can you write down a direct relationship between $n_1$ and $n_2$ counting the vertices?
3. Now use the Handshaking Lemma to count the edges in terms of $n_1, n_2$ and $|V| = 125$ and you get another linear equation in $n_1,n_2$.
4. (2) and (3) yield 2 linear equations in 2 unknowns. Solve them, and you have everything you need.

Please post updates in the comments below if you need more help.