[Math] Graph Theory – Leaves vs. # of vertices degree 3+

Question

I am studying Problem 35, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads…

Prove that a tree always has more leaves than vertices of degree at least 3.

I feel like there should be an inductive argument with respect to n, the amount of vertices, but I don't know how to count the vertices of degree 3+. Does anyone have an idea of how to start this?

Answer 1

Let the tree $T$ have $A_1$ vertices of degree $1$, $A_2$ vertices of degree $2$, etc.

Then $$\sum_v \operatorname{deg}(v) = \sum_{i=1}^n i A_i = 2(n-1).$$ But we know that $\sum_{i=1}^n A_i = n$, so $$\sum_{i=1}^n (i-2)A_i = -A_1 + A_3 + 2A_4 + 3A_5 + \dots = -2.$$ Can you finish it from there?