smallest number of vertices of degree $1$ in tree with $3$ vertices of degree $4$ and $2$ of degree $5$

Question

Find, with proof, the smallest number of vertices of degree $1$ in a tree with $3$ vertices of degree $4$ and $2$ of degree $5$. Provide an example of such a tree.

I'm not sure how to find this. I know that every tree with at least $2$ vertices has at least $2$ leaves, trees are bipartite, trees have no cycles. Also, every tree is connected. But I'm not sure how to make use of these properties to get the desired proof. So far, the smallest value I've been able to come up with is $14,$ though I think that number can be made smaller. My basic idea is to make it so that as many vertices are as "tightly joined or connected" as possible, so as to maximize the number of vertices with degree greater than $1$.

Answer 1

Hint: The main property of a tree you want to use here is its number of edges. A tree with $n$ vertices has $m=n-1$ edges. You can use the fact that the sum of the degree is $2m$ (twice the number of edges) to prove how many degree $1$ vertices you need.

Click the spoiler for a full answer:

Let $T=(V,E)$ be a tree. Consider the sum $\sum_{u\in V} d(v) = 2|E| = 2n-2$. From this we get that $\sum_{u\in V}(d(u) - 2) = -2$. Note that vertices of degree $1$ contribute $-1$ to the left and vertices of degree $2$ contribute $0$. All other vertices add a positive amount to the left. If we have three vertices of degree $4$ and two of degree $5$, this gives us a sum $3\cdot(4-2) + 2\cdot(5-2) = 12$. Thus your figure of $14$ was correct ($-14 + 12 = -2$), you need at least $14$ degree $1$ vertices to make the total left hand side sum to $-2$.

Since your minimum number was correct, I assume you've found a tree that works as an example (any tree with exactly three degree $4$, two degree $5$ and 14 degree $1$ vertices will work).