Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to prove the following claim, given the tree $T=(V,E)$, $|V|=n\geq2$: $$|V_1| = 2 + \sum (j-2)|V_j|$$

where the sum is from $j=3$ up to the highest degree, and $$V_i = \{ x \in V \mid \deg(x) = i\}.$$

This was a bonus question given by my professor. We were sitting on this question for hours and have no idea how to prove it.

Can someone help out with a hint?

Thanks!

share|improve this question
    
I've added LaTeX formatting to your question; apologies if I changed your intended meaning in any way. –  Zev Chonoles Nov 28 '11 at 19:40
    
Thanks! Just like I intended :-) –  Daniel Nov 28 '11 at 19:42

3 Answers 3

up vote 5 down vote accepted

Count the number of edges in two ways.

  • By the Handshake Lemma: $|E|=\frac{1}{2}\sum\limits_{i=1}^\infty i|V_i|$.
  • By the characterization of trees: $|E|= \sum\limits_{i=1}^\infty |V_i|-1$.

    Equate these two quantities, and remember that $|V_1|$ is the number of leaves.

    $\frac{1}{2}\sum\limits_{i=1}^\infty i|V_i|= \sum\limits_{i=1}^\infty |V_i|-1,$

    so

    $\sum\limits_{i=1}^\infty (i-2)|V_i|+2=0$

    so

    $-|V_1|+0+\sum\limits_{i=3}^\infty (i-2)|V_i|+2=0$

    so

    $|V_1|=\sum\limits_{i=3}^\infty (i-2)|V_i|+2$

    which is what you are after.

  • share|improve this answer
        
    Thanks! :) Perfectly understand what you did here, you helped us a lot :) –  Daniel Nov 28 '11 at 21:20

    Prove it by induction on $n$:

    • It's trivial for the case $n=2$. (Why?)
    • The inductive step is to add a vertex and, because it's a tree, you've changed at most three of the $V_i$. (Which ones? How have they changed? Understand this before proceeding.) In the sum, then, you're adding $1$ to the left-hand side and $-(k-2)+(k+1-2)$ for some $k$ to the right, which maintains the equality.
    share|improve this answer
        
    Thanks for your answer. I understood why we will change at most 3 Vi. What I didn't understand is why you are adding -(k-2)+(k+1-2). K represents the Vk that was changed? –  Daniel Nov 28 '11 at 20:11
        
    @Daniel: The rest of the problem should be doable. Do you understand which $V_i$ change and how they change? That will help. –  msh210 Nov 28 '11 at 20:12

    There is a close relationship between your problem and the degree sum formula for graphs. For any finite graph, tree or otherwise, the equation

    $$2|E| = \sum_{v\in V} \deg(v)$$

    always holds. If you haven't proved this before, it's worth stopping to think about why the equation is correct.

    It is possible to transform the equation

    $$|V_1| = 2 + \sum (j-2)|V_j|$$

    into an explicit statement of the degree sum theorem for trees. Hint: $j|V_j|$ is just another way to write $\sum_{v\in V_j} \deg(v)$.

    share|improve this answer

    Your Answer

     
    discard

    By posting your answer, you agree to the privacy policy and terms of service.

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