Prove that in every tree on $n$ vertices there are at most ${n-2\over 3}$ vertices of degree more than three.

Question

I'm trying to show that:

If $T$ is a tree on $n$ vertices, then there are at most ${n-2\over 3}$ vertices that have a degree greater than three.

I've been unable to come up with anything so far that could be insightful or helpful. Any help? Thanks.

Answer 1

PS: I have misread the question, my answer regards the case for vertices of degree greater or equal ($\geq$ ) $3$ and not $>3$:

First of all your formula is wrong, it should be $\frac{n-2}{2}$, e.g. take the 3-star (4 vertices all connected to the center).

To the proof: Try to show it with induction: $n=1,2$ should be clear. For bigger $n$ leave out a leave. This will yield a tree of lower degree. If you decrease the number of vertices of degree greater than 3, you now have a vertex of degree 2 (adjacent to the former leave). But you can now ignore this vertex also (by merging the to adjacent edges) and get a tree with 2 less vertices and the same amount of vertices of degree $\geq 3$. Apply now induction.

Answer 2

Note that a tree on $n$ vertices has $n-1$ edges and therefore $$\sum_{v\in V}\text{deg}(v)=2(n-1).$$ Let $a$ the number of vertices of degree greater than $3$, then $$4a+(n-a)\leq \sum_{v\in V}\text{deg}(v)=2(n-1).$$ which implies $$a\leq \frac{n-2}{3}.$$ This approach can be easily generalized: if $a_d$ is the number of vertices of degree greater than $d\geq 1$ then $$a_d\leq \frac{n-2}{d}.$$