131 views

Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following is true?

1. $s=99$
2. $s=198$
3. $99 \: < \: s \: < \: 198$
4. None of the above
asked | 131 views

Option B)

Take a Skewed tree.

Number of nodes =$n$

Number of nodes having neighbour $1=2( \text{root and the leaf})$

Number of nodes having neighbour $2=98(\text{Remaining Internal Nodes})$

$s=1\times 2+2\times 98=198$

answered by Veteran (15.6k points)