Prove that any tree with $n$ nodes has at least $\frac {n}{2}$ nodes with degree $1$ or $2$. $n \ge 2$

Question

Here is the question:

A tree is a connected simple graph with no cycle.
Prove that any tree with $n$ nodes has at least $\frac {n}{2}$ nodes with degree $1$ or $2$. $n \ge 2$

---

I try to use mathematical induction to prove this with the base case of $2$. Every tree will have $n-1$ edges if there are $n$ vertices. So the Base Case will have at least one node with degree of $1$. However, it seems like it is very hard to prove the $k+1th$ case. Any method to approach this question? Thanks

Answer 1

Suppose that there were fewer than $n/2$ nodes with degree $1$ or $2$. If $n$ is even then this means there are at least $n/2+1$ nodes with degree $3$ or more, and if $n$ is odd then there are at least $(n+1)/2$ nodes with degree $3$ or more. Of course, since trees are connected, the rest of the nodes have degree at least $1$.

Now take the total sum of the degrees. In the even case it is at least $3n/2+3 + n/2-1 = 2n + 2$, so by the handshaking lemma there are at least $n+1$ edges. In the odd case the sum is at least $3(n+1)/2 + (n+1)/2 = 2(n+1) = 2n+2$ as well, so again there are at least $n+1$ edges.

But this is absurd, since we know there are only $n-1$ edges in a tree on $n$ nodes.