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

Given, a forest has 100 vertices and 40 edges.

A tree with 100 vertices has 99 edges.

To convert a forest into a tree, number of edges that should be added = (Number of components - 1)

Let number of components be $x$

$\therefore$  40 + ($x$ - 1) = 99

$x$ = 60

Answer 2

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