# Smallest number of vertices in tree with specific degrees.

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

• @RobPratt using the handshaking lemma, I get something like $r = 12 + \dfrac{n_1}2 + n_2 + \dfrac{5}2 n_5$, but I can't seem to get a good lower bound for this. Perhaps considering cases when $n_5 = 0, 1, 2,$ etc. might help? Nov 14 '20 at 3:15

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