Consider the following directed graph: Which of the following is/are correct about the graph?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2021 Set 2 · Q46
Time

Select all that applyOne or more correct
Solution
Official answer: A) The graph does not have a topological order.; B) A depth-first traversal starting at vertex S classifies three directed edges as back edges.
Graph TraversalsLet us analyze each statement based on standard graph theory and traversal properties:
Topological Order (Option A): A directed graph has a topological ordering if and only if it is a Directed Acyclic Graph (DAG). The given graph contains directed cycles (for example, the cycle formed by vertices in the grid). Since it contains at least one cycle, it is not a DAG, and therefore does not have a topological order. Hence, Option A is correct.
Back Edges in DFS (Option B): A depth-first traversal starting from vertex reaches all vertices. In any DFS tree of this graph, the DFS tree contains tree edges. Out of the remaining non-tree edges encountered during traversal, exactly directed edges point from a descendant to an ancestor, which classifies them as back edges (corresponding to the fundamental cycles). Thus, Option B is correct.
Strongly Connected Component (Option C): Every directed graph has at least one strongly connected component (SCC) (trivially, even single vertices are SCCs if there are no larger ones, and here non-trivial SCCs exist as well). Thus, the statement that the graph does not have an SCC is false. Hence, Option C is incorrect.
Strong Connectivity of the Entire Graph (Option D): For each pair of vertices and to have a directed path between them, the entire graph would need to be strongly connected. Since the graph is not strongly connected (for instance, the top-right vertices have no path back to ), this statement is false. Hence, Option D is incorrect.
Therefore, the correct options are A and B.
Try the question first, then check your work.
Examiner trap
Recall that a topological sort exists if and only if the directed graph is acyclic. Also, every directed graph can be partitioned into one or more strongly connected components.
This Graph Traversals previous year question is Q46 of the GATE CSE 2021 Set 2 paper. Find more GATE CSE PYQs on Graph Traversals in Algorithms, 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 Traversals 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 Traversals has 16 GATE CSE PYQs across 12 papers from 2014 to 2026. 5 of them are 2-mark MSQs like this one, and it is the only one in GATE CSE 2021 Set 2.
How GATE tests Graph TraversalsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.