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 …
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2024 Set 1 · Q60
Time
Your answerNumerical answer
Solution
Official answer: 60
Graph TheoryA DFS traversal on an undirected graph with vertices and connected components produces a DFS spanning forest consisting of trees.
Let the -th connected component have vertices. The DFS tree spanning this component has edges.
The total number of edges in the DFS forest is the sum of edges across all trees:
Given and :
Therefore, the number of connected components in is 60.
Try the question first, then check your work.
Examiner trap
A spanning forest of a graph with vertices and components has exactly edges.
This Graph Theory previous year question is Q60 of the GATE CSE 2024 Set 1 paper. Find more GATE CSE PYQs on Graph Theory in Engineering Mathematics, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Graph Theory PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Graph Theory has 21 GATE CSE PYQs across 14 papers from 2012 to 2026. 7 of them are 2-mark NAT questions like this one, and GATE CSE 2024 Set 1 has 3.
How GATE tests Graph TheoryIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.