How many vertices of degree 1 in a tree?

Question

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.

Answer 1

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

Answer 2

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