GATE CSE 2024 | Set 1 | Question: 50

Question

The number of edges present in the forest generated by the $\text{DFS}$ traversal of an undirected graph $G$ with $100$ vertices is $40$. The number of connected components in $G$ is __________.

Answer 1

The number of connected components in G is same as number of connected components in the forest generated by DFS traversal.

A forest with 100 vertices and 0 edges has 100 components.

Adding 1 edge will reduce the number of components by 1, as an additional edge will connect 2 components. Remember the resulting graph has to be a forest, it cannot have any cycle, i.e. we can only add the edge between vertices that belong to different components.

Repeatedly adding 1 edge 40 times, results in reduction of number of components by 1, 40 times. That means we will end up with 100 - 40 = 60 connected components.

Answer - 60