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