GateAI
Graph Traversals

GATE CSE 2021 Set 2 · Q46

MSQ2 marksMedium

Time

Consider the following directed graph: Which of the following is/are correct about the graph?

GATE CSE 2021 Set 2 Q46 diagram

Select all that applyOne or more correct

Pick every correct option

Solution

Step-by-step verified 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 Traversals

Let us analyze each statement based on standard graph theory and traversal properties:

  1. 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.

  2. Back Edges in DFS (Option B): A depth-first traversal starting from vertex SS reaches all 1616 vertices. In any DFS tree of this graph, the DFS tree contains 1515 tree edges. Out of the remaining non-tree edges encountered during traversal, exactly 33 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.

  3. 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.

  4. Strong Connectivity of the Entire Graph (Option D): For each pair of vertices uu and vv 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 SS), 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.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

Where do you stand for GATE?

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.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Graph Traversals in GATE CSE

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 Traversals

More from GATE CSE 2021 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 2 · Q46 · MSQ

Consider the following directed graph: Which of the following is/are correct about the graph?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.