# Graph Theory - Leaves vs. # of vertices degree 3+

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?

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?
• Thank you for your response, but I am confused by your last sum. What's the purpose of it and why is it $-2$? – Scott Nov 22 '13 at 1:50
• It gives a relationship between the number of vertices of a given degree. If you like, rearranged it becomes $A_1 = 2 + A_3 + 2A_4 + 3A_5 + \dots$. Since each $A_i \geq 0$, this immediately gives the bound that every tree has at least $2$ leaves. If you consider the relationship between $A_1$ and $A_3$ you get your bound... – Michael Biro Nov 22 '13 at 1:54
• Oh! I don't know why that didn't click before. Thank you for your help with this problem. But just to clarify, as well as have this answer on Math.SE for posterity... Since $A_{1} = A_{3} + C$, where C is some positive integer, representing the amount of vertices that aren't leaves or have degree 3. This means that $A_{1}>A_{3}$. – Scott Nov 22 '13 at 2:33