GATE 2024 CS1 Q.60: solution and answer

Official answer: 60Source: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. DFS traversal of an undirected graph produces a spanning forest: it visits every vertex, and within each connected component the DFS tree edges form a spanning tree of that component.

2. A spanning tree on a component with $k$ vertices has exactly $k-1$ tree edges.

3. Summing over all connected components: total forest edges $={\sum }_i(k_i-1)=n-c$, where $n$ is the total number of vertices and $c$ is the number of connected components.

4. Given $n=100$ and total forest edges $=40$: $$40=100-c$$

5. Solving: $$c=100-40=60$$