maximum number of leafs in a tree with degrees at most 3.

Question

Let $T=(V,E)$ be a tree such that $10\leq|V|$ and $1\leq deg(u)\leq 3$ for each $u\in V$. What is a good upper bound for number of leafs in $T$ ? Is is true that $\# leafs\leq |V|-4$ ?

Answer 1

Euler's formula gives you $V-E+F=2$, for a tree $F=1$, hence $E=V-1$. We also know that the sum over the degrees of all vertices is equal to $2E$, so $\sum_{u\in V}\deg(u)=2V-2$. Let $L$ denote the number of leaves, then $$ L + \sum_{u\in V \setminus L}\deg(u)=2V-2 $$ As $\deg(u) \le 3$ we can estimate $$ L + 3(V-L) \ge 2V-2 $$ which gives $L \le \frac{V+2}{2}$. This bound is best possible and attained whenever all non leaf vertices have degree $3$.