GATE CS 2026 Set 1 Q40 — Graph Traversals (BFS, DFS)

To determine which options can never be correct for a directed edge $(u, v) \in E$ in a Directed Acyclic Graph (DAG) $G$, we analyze the relationship between the discovery interval $[d[x], f[x]]$ and finishing interval of vertices $u$ and $v$ during Depth-First Search (DFS).

1. The Parenthesis Theorem

For any two vertices $u$ and $v$ in a graph, their active intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ must satisfy exactly one of the following conditions:

• Disjoint: The intervals are entirely separate, i.e., $d[u] < f[u] < d[v] < f[v]$ or $d[v] < f[v] < d[u] < f[u]$.
• Nested: One interval is entirely contained within the other, i.e., $d[u] < d[v] < f[v] < f[u]$ or $d[v] < d[u] < f[u] < f[v]$.

Intervals can never partially overlap. Therefore, the relation $d[u] < d[v] < f[u] < f[v]$ is impossible for any pair of vertices in any graph. This makes Option D impossible.

2. Classification of Edges in a DAG

For a directed edge $(u, v) \in E$, the type of edge determines the interval relationship:

• Tree / Forward Edge: $u$ is an ancestor of $v$ in the DFS forest. This corresponds to the nested interval $d[u] < d[v] < f[v] < f[u]$. This matches Option A, which is possible.
• Cross Edge: $v$ is visited and finished before $u$ is discovered. This corresponds to the disjoint interval $d[v] < f[v] < d[u] < f[u]$. This matches Option C, which is possible.
• Back Edge: $v$ is an ancestor of $u$ in the DFS forest. This corresponds to the nested interval $d[v] < d[u] < f[u] < f[v]$. However, a back edge $(u, v)$ implies a directed cycle in the graph. Since $G$ is a DAG (Directed Acyclic Graph), it cannot contain any back edges. Thus, this relation is impossible, making Option B impossible.

Conclusion

The options that can NEVER be correct are B and D.