How to approach this discrete graph question about Trees.

Question

A tree contains exactly one vertex of degree $d$, for each $d\in\{3, 9, 10, 11, 12\}$.

Every other vertex has degrees $1$ and $2$. How many vertices have degree $1$?

I've only tried manually drawing this tree and trying to figure it out that way, however this makes the drawing far too big to complete , I'm sure there are more efficient methods of finding the solution.

Could someone please point me in the right direction!

Answer 1

Suppose there are $n_1$ vertices of degree $1$ and $n_2$ vertices of degree $2$.

• How many vertices are there total?
• If the graph is a tree, how many edges should it have?
• What is the sum of the degrees?

Answer 2

Let $n_d$ be the number of nodes of degree $d$, and let $n$ be the total number of nodes. Then $\sum_d n_d = n$ and $\sum_d d n_d = 2(n-1)$, so $$\sum_d (d-2) n_d = -2,$$ equivalently, $$n_1 = 2+\sum_{d\ge 3} (d-2) n_d.$$ Now substitute the known values $n_d=1$ for $d\in\{3,9,10,11,12\}$ and $n_d=0$ for $d >3$ otherwise, yielding \begin{align} n_1 &= 2+(3-2)n_3+(9-2)n_9+(10-2)n_{10}+(11-2)n_{11}+(12-2)n_{12} \\ &= 2+1+7+8+9+10 =37. \end{align}