8
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ I've added LaTeX formatting to your question; apologies if I changed your intended meaning in any way. $\endgroup$ Nov 28, 2011 at 19:40

3 Answers 3

12
$\begingroup$

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.

  • $\endgroup$
    1
    • $\begingroup$ Thanks! :) Perfectly understand what you did here, you helped us a lot :) $\endgroup$
      – Daniel
      Nov 28, 2011 at 21:20
    2
    $\begingroup$

    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.
    $\endgroup$
    2
    • $\begingroup$ 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? $\endgroup$
      – Daniel
      Nov 28, 2011 at 20:11
    • $\begingroup$ @Daniel: The rest of the problem should be doable. Do you understand which $V_i$ change and how they change? That will help. $\endgroup$
      – msh210
      Nov 28, 2011 at 20:12
    1
    $\begingroup$

    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)$.

    $\endgroup$

    You must log in to answer this question.

    Not the answer you're looking for? Browse other questions tagged .