3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thank you for your response, but I am confused by your last sum. What's the purpose of it and why is it $-2$? $\endgroup$ – Scott Nov 22 '13 at 1:50
  • $\begingroup$ 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... $\endgroup$ – Michael Biro Nov 22 '13 at 1:54
  • $\begingroup$ 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}$. $\endgroup$ – Scott Nov 22 '13 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.