2
$\begingroup$

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to

$$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 \big)}$$

A pendant vertex is a vertex of degree $1$.

To make sense out of this equation we try $n=2$ then we only have one edge connecting these two vertices and the number of pendant vertices is equal to $2$ just as the formula suggests.

Now if $n=3$ then we have two edges, one vertex has degree of $2$ and still two vertices with degree $2$ also as the formula suggests.

But I can't understand why we have that summation and it only takes the vertices with degree greater than or equal to $3$. Can I prove this formula by induction ?

I know that $$\large{\sum_{i=1}^n = deg(v_i) = 2(n-1)= 2n-2}$$ since the number of edges for a tree $T$ with $n$ vertices is $n-1$ and also from this we get that $$\large{\sum_{i=1}^n = deg(v_i)-2 = \sum_{i=1}^n deg(v_i) + \sum_{i=1}^n -2= (2n-2) + (-2n) = -2}$$.

So I feel like I am close somehow but still couldn't get it. Also the formula that I am trying to derive is suggesting that every tree with at least two vertices must have at least $2$ pendant vertices, Why is that true ?

$\endgroup$
  • $\begingroup$ You can sum over vertices of degree $2$ as well, but they only contribute $0$ to the sum. $\endgroup$ – Casteels Nov 6 '15 at 4:50
  • $\begingroup$ @Casteels , Yes that is true $\endgroup$ – alkabary Nov 6 '15 at 4:58
3
$\begingroup$

Let $P$ be the number of degree 1 vertices. Then $$-2=\sum(\deg(v)-2)=\sum_{\deg(v)=1}(-1)+\sum_{\deg(v)=2}0+\sum_{\deg(v)\ge3}=-P+\sum_{\deg(v)\ge3}$$ and we're done.

$\endgroup$
  • $\begingroup$ That's very very very smart , thanks a lot sir @Gerry Myerson $\endgroup$ – alkabary Nov 6 '15 at 6:32

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.