How many vertices of degree 1 in a tree? How many vertices of degree 1 are there in a tree with no vertices of degree more than 4?
The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of vertices. Any help would be appreciated. Thanks in advance.
 A: Let $k$ be the number of leafs in the tree. Let $n$ be the number of vertices.
It is known that $k \geq 2$ with equality for $T=P_n$.
As for the upper bound, the sum of degrees is at most $k+4(n-k)$. Thus 
$$2(n-1)\leq k+4(n-k)=4n-3k \,$$
Solving this equality we get 
$$k \leq \frac{2n+2}{3} \,.$$
Since $k$ is integer, we must have
$$k \leq \lfloor \frac{2n+2}{3} \rfloor \,.$$
The upper bound can be reached. Let $r$ be the remainder when $2n+2$ is divided by $3$. Then (as the above proof suggests) we need to construct a tree with $\lfloor \frac{2n+2}{3} \rfloor$ leafs, $r$ vertices of degree $2$ and $n-r- \lfloor \frac{2n+2}{3} \rfloor$ vertices of degree $4$. You can prove that such a tree exists by induction on $n$, the $P(n) \Rightarrow P(n+3)$ is easy (replace a leaf by a vertex of degree $4$ and connect it to 3 new leafs.) 
A: If there are $n_i$ vertices of degree $i$, $1\le i\le 4$, then we must  have $$n_1+2n_2+3n_3+4n_4=2(n-1)=2(n_1+n_2+n_3+n_4-1),$$
hence $$n_1=n_3+2n_4+2. $$
Especially, 
$$ 2\le n_1\le \frac{2n+2}3.$$
(The latter from $3n_1= 2(n_1+n3+n_4)+2-n_3\le 2n+2$).
