What are common examiner traps in Graph Traversals?

Assuming an undirected graph DFS tree can contain cross edges (in undirected graphs, all non-tree edges are back/forward edges). Confusing back-edge timestamp condition (d[v] < d[u] < f[u] < f[v]) with forward-edge condition (d[u] < d[v] < f[v] < f[u]). Believing the root of a DFS tree is always or never an articulation point (it is an AP if and only if it has ≥ 2 children in the DFS tree). Assuming BFS tree height equals graph diameter diam(G) instead of being bounded below by ⌈ diam(G)/2 ⌉. Assuming DFS tree paths represent shortest paths (DFS does not compute shortest paths). Allowing partially overlapping timestamp intervals [d[u], d[v], f[u], f[v]], which violates the Parenthesis Theorem for any DFS.

GATE CSE Graph Traversals PYQs

Q: What does GATE test in Graph Traversals?

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, back, forward, cross edges), timestamp intervals via the Parenthesis Theorem, DAG topological orderings, and structural invariants like the BFS level difference inequality and tree height versus graph diameter. Recent papers heavily favor MSQs and multi-property conceptual deductions over simple single-answer lookups.

Standard yield12.9% of Algorithms

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, b… Read the guide

Take topic test

Questions: 16
Asked: since 2014
Total marks: 24
Marks / paper: 1

16 GATE CSE Graph Traversals PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2026 Set 1 · Q50Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishing time, respectively, of the vertex $v \in V$ . Suppose that the input directed graph $G(V, E)$ is a directed acyclic graph…MSQ2 marksMediumDiagramSolve
GATE CSE 2026 Set 1 · Q55An undirected, unweighted, simple graph $G(V, E)$ is said to be 2-colorable if there exists a function $c: V \rightarrow \{0, 1\}$ such that for every $(u, v) \in E$ , $c(u) \neq c(v)$ . Which of the following statements about 2-colorable graphs is/are true?MSQ2 marksEasySolve
GATE CSE 2025 Set 1 · Q43Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$ . Let the maximum value of $d(u, v)$ , $u, v \in V$ such that $u \neq v$ , be 30. Let $T$ be any breadth-first-search tree of $G$ .…MCQ2 marksMediumSolve
GATE CSE 2025 Set 2 · Q29Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?MSQ1 markMediumSolve
GATE CSE 2025 Set 2 · Q59Consider the following algorithm someAlgo that takes an undirected graph $G$ as input. someAlgo(G) 1. Let $v$ be any vertex in $G$ . Run BFS on $G$ starting at $v$ . Let $u$ be a vertex in $G$ at maximum distance from $v$ as given by the BFS. 2. Run BFS on $G$ again with $u$ …NAT2 marksMediumDiagramSolve
GATE CSE 2024 Set 1 · Q45Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$ . Suppose $T$ is also a breadth first search (BFS) tree in $G$ , rooted at $v$ . Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?MSQ2 marksMediumSolve
GATE CSE 2021 Set 1 · Q41An $\textit{articulation point}$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a DFS tree obtained by doing DFS in a connected undirected graph $G$ . Which of the following options is/are correct?MSQ2 marksMediumSolve
GATE CSE 2021 Set 2 · Q46Consider the following directed graph: Which of the following is/are correct about the graph?MSQ2 marksMediumDiagramSolve
GATE CSE 2017 Set 2 · Q15The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?MCQ1 markMediumDiagramSolve
GATE CSE 2016 Set 1 · Q11Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _________.NAT1 markEasyDiagramSolve
GATE CSE 2015 Set 1 · Q45Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$ , let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$ . A breadth first search (BFS) is performed starting at $s$ . Let $T$ be the resultant BFS tree. If $(u,v)$ is an edge…MCQ2 marksMediumSolve
GATE CSE 2014 Set 1 · Q3Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as $G$ ?MCQ1 markEasySolve
GATE CSE 2014 Set 1 · Q11Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$ , when $G$ is represented as an adjacency matrix?MCQ1 markEasySolve
GATE CSE 2014 Set 1 · Q13Consider the directed graph given below. Which one of the following is TRUE?MCQ1 markEasyDiagramSolve
GATE CSE 2014 Set 2 · Q14Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computingMCQ1 markEasySolve
GATE CSE 2014 Set 3 · Q13Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _______.NAT1 markMediumDiagramSolve

What GATE tests in Graph Traversals

Concepts, patterns, formulas and traps distilled from past papers.

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, back, forward, cross edges), timestamp intervals via the Parenthesis Theorem, DAG topological orderings, and structural invariants like the BFS level difference inequality and tree height versus graph diameter. Recent papers heavily favor MSQs and multi-property conceptual deductions over simple single-answer lookups.

Core concepts

DFS timestamping (d[v], f[v]) and the Parenthesis Theorem
Edge classification: Tree, Back, Forward, and Cross edges
Absence of back edges in DAGs and absence of cross edges in undirected DFS
BFS Shortest Path Tree property and BFS non-tree edge distance constraints
Topological sorting via in-degree reduction or reverse DFS finish times
Articulation point conditions in DFS trees (root child count ≥ 2, back edge reachability)
Bipartite graph / 2-colorability testing using BFS/DFS
Transpose graph (GT) reachability and Strongly Connected Components
Graph Diameter computation via double BFS

Recurring question patterns

DFS Edge Classification and Parenthesis Theorem
CommonMSQ2 marks2026, 2025, 2024, 2021
Evaluating valid/invalid discovery and finishing timestamp orderings $[d(u), f(u)]$ or identifying tree/back/forward/cross edge counts in directed graphs vs DAGs vs undirected graphs.
BFS Metric and Distance Properties
Commonmixed1.5 marks2025, 2017, 2015, 2014
Questions leveraging BFS shortest path properties, level bounds for non-tree edges ( $|d(u) - d(v)| \le 1$ ), queue order validation, and graph diameter vs BFS tree height bounds.
Topological Sort Existence and Counting
Commonmixed1 marks2021, 2016, 2014
Determining valid topological sort sequences, counting possible topological orderings for independent DAG paths via multiset permutations, or checking DAG cycle conditions.
Graph Connectivity and DFS Tree Structures (Articulation Points, SCCs, 2-Colorability)
CommonMSQ2 marks2026, 2025, 2021, 2014
Analyzing structural components identified by traversals: root/leaf articulation point conditions in DFS trees, transpose graph SCC invariance, bipartite 2-coloring, and tree diameter algorithms.
Traversal Complexity and Maximum Recursion Depth
Occasionalmixed1 marks2026, 2014
Analyzing runtime under adjacency list $\Theta(|V| + |E|)$ vs adjacency matrix $\Theta(|V|^2)$ , or finding worst-case DFS stack/recursion depth in specific graph topologies.

Formulas GATE uses

BFS Edge Distance Inequality

|d(s, u) - d(s, v)| \le 1 \quad \forall (u, v) \in E

Determining possible level differences between endpoints of any edge in an unweighted undirected BFS tree.

BFS Tree Height vs Graph Diameter

h(T) \ge \left\lceil \frac{\text{diam}(G)}{2} \right\rceil

Finding lower bounds on the height of any BFS tree given the maximum pairwise shortest distance in an undirected graph.

Independent DAG Chains Topological Sort Count

\frac{(k_1 + k_2 + \dots + k_m)!}{k_1! \, k_2! \cdots k_m!}

Counting distinct topological orderings when intermediate DAG components form $m$ disjoint independent linear chains.

DFS Timestamp Interval Inclusion (Parenthesis Theorem)

v \text{ is a proper descendant of } u \iff d[u] < d[v] < f[v] < f[u]

Relating ancestor/descendant relationships and classifying tree/back/forward edges using discovery and finish timestamps.

DFS / BFS Time Complexity

T(V, E) = \Theta(|V|^2) \text{ (Matrix)}, \quad T(V, E) = \Theta(|V| + |E|) \text{ (List)}

Evaluating algorithm runtimes for connectivity, topological sorting, and 2-colorability under various representations.

Examiner traps in Graph Traversals

Assuming an undirected graph DFS tree can contain cross edges (in undirected graphs, all non-tree edges are back/forward edges).
Confusing back-edge timestamp condition (d[v] < d[u] < f[u] < f[v]) with forward-edge condition (d[u] < d[v] < f[v] < f[u]).
Believing the root of a DFS tree is always or never an articulation point (it is an AP if and only if it has ≥ 2 children in the DFS tree).
Assuming BFS tree height equals graph diameter diam(G) instead of being bounded below by ⌈ diam(G)/2 ⌉.
Assuming DFS tree paths represent shortest paths (DFS does not compute shortest paths).
Allowing partially overlapping timestamp intervals [d[u], d[v], f[u], f[v]], which violates the Parenthesis Theorem for any DFS.

How questions are asked

MSQ property verification for BFS vs DFS characteristics
NAT counting of valid topological orderings in a given DAG
NAT calculating longest recursion path / tree diameter
MCQ identifying valid BFS/DFS queue or visit sequences
MSQ timestamp inequality validation using the Parenthesis Theorem
MCQ bounding BFS tree height from graph diameter

Paper trends

Shift from direct 1-mark MCQs (e.g., matrix traversal asymptotic runtime, direct queue orders) to rigorous 2-mark MSQs exploring edge incompatibilities (e.g., why a tree cannot be both BFS and DFS when forward edges exist).
2026, 2025, 2024, 2021, 2014
Introduction of analytical graph metric problems, combining BFS properties with metric graph theory concepts such as tree height vs diameter and two-sweep diameter algorithms.
2025
Deepening emphasis on formal DFS timestamp interval definitions ( $d[v], f[v]$ ) rather than manual hand-execution traces.
2026

Difficulty notes

Easy questions ask for standard traversal complexities ( $\Theta(n^2)$ for matrix), basic queue ordering checks, or topological sort verification on small DAGs. Medium questions involve DFS timestamp interval logic, MSQ edge classification across directed vs undirected graphs, articulation point structural rules, BFS non-tree edge constraints, and diameter-to-height bounds.