Question
If G is a forest with n vertices and k connected components, how many edges does G have?
Answer: Option C
Was this answer helpful ?
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