Sail E0 Webinar
Question

If G is a forest with n vertices and k connected components, how many edges does G have?   


Options:
A .  [n / k]
B .  [n / k]
C .  n - k
D .  n - k + 1
Answer: Option C

Let `n_1`, `n_2`,.....`n_k` be the number of vertices respectively in K connected components of a
forest G,

then `n_1` - 1, `n_2`- 1,.....,`n_k` - 1  be the number of edges respectively in K  connected
components and

 `n_1` + `n_2` +..... + `n_k` = n (number of vertices in G) 

 Hence, number of edges in G = number of edges in K connected components

= (`n_1` - 1) + (`n_2` - 1`) +...... + (`n_k`) - 1  = n - k




Was this answer helpful ?

Submit Solution

Your email address will not be published. Required fields are marked *

Latest Videos

Latest Test Papers