Tree-related problem, counting leafs

Question

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the number of nodes is 18, and has no nodes of degree 2, has 13 or 14 leafs. How does one prove this? It seems like an easy one, and I tried combining handshaking lemma and summing up the nodes of degrees 1 through 6, excluding degree 2, which alltogether give the number of nodes(18), and that way I got system of equations. However, I struggle to show that the number of leafs is 13 or 14. Can someone help on this one? Thanks in advance.

Answer 1

Let $w$ be the number of leaves. We know $\sum \deg(v)=34$ where the sum is taken over the $18$ vertices of the graph. Each leaf of the graph contributes a degree of $1$; and each non-leaf contributes a degree between $3$ and $6$ inclusive, with at least one vertex contributing a degree of $6$.

So $6+w+3(17-w)\le \sum\deg(v) \le 6+w+6(17-w)$

Therefore $$57-2w\le 34 \le 108-5w $$

Taking these inequalities separately, $57-2w\le 34\Rightarrow w\ge 11.5$.

And $34\le 108=5w \Rightarrow w\le 14.8$

Since $w$ is an integer, we must have $12\le w \le 14$.

In fact I was able to draw graphs with all these possibilities. So I would say that the possible number of leaves is $12, 13$, or $14$. (Not just $13$ or $14$).