Show that the number of leaves in a tree equals to $\frac{1}{2}\left(\sum_{v\in V}|\text{deg}(v)-2|+1\right).$

151 Views Asked by At

Show that the number of leaves in tree equals to. $$\frac{1}{2}\left(\sum_{v\in V}|\text{deg}(v)-2|+1\right).$$

I know the theorems,

  • For any graph, $\sum_{v\in V} \text{deg}(v) = 2 \left\vert E \right\vert$ holds.

  • For any tree, $\left\vert V \right\vert=\left\vert E \right\vert + 1$ holds.

The difficult thing for me to approach about the expression of the given problem is that I must care about "absolute value" expression. $\quad i.g. \quad \left\vert \text{deg}(v)- 2 \right\vert$

Because, if there is Not the absolute value expression, below

$$\sum_{i=1}^{k} \text{deg}(v_i) - 2 = 2\left\vert E \right\vert - 2k.$$

but, as absolute symbol is, I must consider each cases.

I need a hint to approach this problem, please.

1

There are 1 best solutions below

0
On

Let $V_1$ be the vertices of degree $1$, i.e. the set of leaves. Then \begin{align} \sum_{v\in V}|\text{deg}(v)-2|&=\sum_{v\in V-V_1}(\text{deg}(v)-2)+\sum_{v\in V_1}|1-2|\\ &=\sum_{v\in V-V_1}\text{deg}(v)-2(|V|-|V_1|)+|V_1|\\ &=\sum_{v\in V}\text{deg}(v)-2(|V|-|V_1|)\\ &=2|E|-2(|E|+1)+2|V_1|=-2+2|V_1|. \end{align} Hence $$|V_1|=\frac{1}{2}\left(\sum_{v\in V}|\text{deg}(v)-2|+1\right).$$