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 ?
Best Answer
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.