Find, with proof, the smallest number $r$ of vertices in a tree having two vertices of degree $3$, one vertex of degree $4$, and two vertices of degree $6$. Give an example of such a tree.
Clearly, I need to make use of the degree requirements to impose a lower bound on the number of vertices. Intuitively, I think the higher the average degree, the more vertices there'll be as compared with graphs with lower degree. I know a few properties about trees, including the fact that every tree with at least two vertices has at least $2$ leaves. Trees are connected graphs without cycles. So far, the smallest number I can find is $19,$ and that is by placing the vertex of degree $6$ at the root and by making the other vertices as neighbours. But this approach seems too simple; it's likely that the minimum number is smaller. Clearly it's greater than $7$.
Best Answer
For $d \ge 1$, let $n_d$ be the number of vertices of degree $d$. Then we have \begin{align} r &=\sum_d n_d \\ 2(r-1)&=\sum_d d n_d \end{align} By eliminating $r$, we find that $$2\sum_d n_d = 2 + \sum_d d n_d,$$ equivalently, $$0 = 2 + \sum_d (d-2) n_d.$$ We are given $n_3 = 2$, $n_4 = 1$, and $n_6 = 2$, so \begin{align} 0 &= 2 - 1n_1 + 0n_2 + 1n_3 + 2n_4 + 3n_5 + 4n_6 + \sum_{d \ge 7} (d-2) n_d \\ &= 2 -n_1 + 0 + 2 + 2 + 3n_5 + 8 + \sum_{d \ge 7} (d-2) n_d \\ &= 14 -n_1 + 3n_5 + \sum_{d \ge 7} (d-2) n_d. \end{align} Hence $$n_1 = 14 + 3n_5 + \sum_{d \ge 7} (d-2) n_d \ge 14,$$ and so $$r \ge n_1 + n_3 + n_4 + n_6 \ge 14 + 2 + 1 + 2 = 19.$$