834 views
4 votes
4 votes

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

2 Answers

4 votes
4 votes

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$

0 votes
0 votes
Option B

s in the above question is nothing but the sum of degrees of a graph with Δ(maximum degree) <=100 and δ(minimum degree)>=1.

We know that no of edges in a tree with V nodes is V-1 , here 100-1 =99 edges

By Handshaking lemma , sum of degrees (s)= 2*no of edges=198

Related questions

11 votes
11 votes
1 answer
1
go_editor asked May 23, 2016
957 views
Let $G=(V, E)$ be a graph where $\mid V \mid =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Cons...
14 votes
14 votes
2 answers
3