Prove that in every tree, the number of leaves is larger by at least two than the number of vertices with a degree of at least 3.
Trying induction, I get something that is too short to be right, and I don't see how to use $\sum d(v)=2(n-1)$ because we have to prove here that $\displaystyle\sum_{d(v)=1}1 \ge \sum_{d(v)\ge 3}1+2 $ and there's no accounting here for the $d(v)=2$.
Another thing I noticed is that every vertex in a tree such that $d(v) > 1$ leads to an amount $> 1$ of leaves. So for every single $d(v)=3$ there will be at least two leaves. But can I prove that? any hints?
Best Answer
HINT: Suppose that $v$ is a vertex of degree $2$ connected to vertices $u$ and $w$; if you remove $v$ and join $u$ and $w$ by an edge, you don’t change the degree of any of the remaining vertices, and you still have a tree. Repeat this process until you have no vertices of degree $2$. Now let $\ell$ be the number of leaves and express $\sum_v\deg v$ for the reduced tree in two different ways.