0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @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? $\endgroup$ Nov 14 '20 at 3:15
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.