Prove that if $T$ has only vertices of degree 1, 2 and 3, and $T$ has exactly 10 vertices of degree 3, then $T$ has 12 leaves. Here is the original problem:

Consider a tree $T$ that has only vertices of degree 1, 2 and 3.  Suppose that $T$ has exactly 10 vertices of degree 3.  Find and prove how many leaves $T$ has.

My Thoughts
I know that any tree $T$ satisfying those conditions has 12 leaves, but I'm not really sure how to prove it.  I believe you first have to start with a vertex.  Then, place three vertices around this vertex to make a vertex of degree 3.  Repeat this step, making sure the graph is a tree (no cycles and loops).
Any comments or thoughts?
 A: Hint.  The number of vertices of degree $2$ is irrelevant.  Can you see why?
So, assume there are no vertices of degree $2$, then follow the ideas other people have suggested.
A: If I were going to prove it, I would combine these two observations:


*

*A tree on $n$ vertices has $n-1$ edges.

*The sum of the degrees of the vertices is equal to twice the number of edges (i.e., the Handshaking Lemma).
A: Let $n$ be the number of vertices, and $n_k$ the number of vertices of degree $k$, $k=1,2,3$. Let $m$ be the number of edges.


*

*Because $T$ is a tree, we have $m=n-1$.

*Because all the edges have two ends, we have $$2m=n_1+2n_2+3n_3.$$

*We are given that $n_3=10$, and the number of leaves is $n_1$. Solve it from the resulting system of equations. If you are lucky, the answer will not depend on the unknown $n_2$.

A: Here is a more hands-on or algorithmic approach. First, a reduction you can make is to note that the degree 2 vertices are essentially irrelevant, so (up to contracting those edges; i.e. going from $x-y-z$ to $x-z$ for every degree 2 vertex $y$) we may assume we only have those 10 degree 3 vertices and some leaves.
Let us assume we have made this reduction. Then we can recursively compute the number of leaves as follows. Call our original tree $T_0$ and let $L_0$ be the number of leaves. Take a tree with 10 degree 3 vertices. Then there is a degree 3 vertex $v_0$ with two leaves; delete the leaves to get a new tree $T_1$ which only has 9 degree 3 vertices. Since we lost two leaves but gained one (in the form of $v_0$), the number of leaves $L_1$ of $T_1$ is $L_1=L_0-1$. Iterating this, we end up with $T_9$ which has a single degree 3 vertex, hence 3 leaves. Then $3=L_9=L_8-1=\ldots=L_0-9$, so $L_0=12$.
