Question

The number of edges present in the forest generated by the DFS traversal of an undirected graph \( G \) with 100 vertices is 40. The number of connected components in \( G \) is \_\_\_\_\_.

Answer 1

Step 1: Understand the relationship between connected components and edges in a DFS forest. In a connected component, the number of edges is one less than the number of vertices. For \( C \) connected components, the number of vertices in each component can be written as: \[ n_1, n_2, \ldots, n_C, \] where \( n_1 + n_2 + \cdots + n_C = 100 \). The total number of edges in the graph is: \[ \text{Total edges} = (n_1 - 1) + (n_2 - 1) + \cdots + (n_C - 1) = 100 - C. \] Step 2: Compute the number of connected components. Given that the number of edges is 40: \[ 100 - C = 40 \implies C = 60. \] Final Answer: \[ \boxed{60} \]