Prove that the number degree $3$ vertices is less than half of the total number of vertices in a tree.

Question

How do I prove the following:

$$|\{v\in V : \deg(v)\geq 3\}|<\frac{|V|}{2}$$ is true for all trees $T$.

I don‘t how to approach this exercise. Does anyone have a hint perhaps?

Answer 1

Let $k$ be the number of nodes with degree at least $3$ and $n=|V|$. The handshake lemma gives us
$2n-2=\sum_{v\in V} \deg(v)=\sum_{v\in V, \deg(v)\leq 2} \deg(v)+\sum_{v\in V, \deg(v)\geq 3} \deg(v)\geq 3k+n-k$.
This implies
$\Rightarrow 2k+n\leq 2n-2$
$\Rightarrow 2k\leq n-2$
$\Rightarrow k\leq \frac{n}{2}-1<\frac{n}{2}$