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.

Graph Traversals

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.

16 Qs · since 2014 · 24 marks · 1 marks/paperStandard yield

Take topic test

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… Guide

Type

GATE CSE 2026 Set 1Q50MSQ2 marksMediumDiagramConsider 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…
GATE CSE 2026 Set 1Q55MSQ2 marksEasyAn 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?
GATE CSE 2025 Set 1Q43MCQ2 marksMediumLet $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$ .…
GATE CSE 2025 Set 2Q29MSQ1 markMediumWhich of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?
GATE CSE 2025 Set 2Q59NAT2 marksMediumDiagramConsider 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$ …
GATE CSE 2024 Set 1Q45MSQ2 marksMediumLet $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$ ?
GATE CSE 2021 Set 1Q41MSQ2 marksMediumAn $\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?
GATE CSE 2021 Set 2Q46MSQ2 marksMediumDiagramConsider the following directed graph: Which of the following is/are correct about the graph?
GATE CSE 2017 Set 2Q15MCQ1 markMediumDiagramThe 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?
GATE CSE 2016 Set 1Q11NAT1 markEasyDiagramConsider the following directed graph: The number of different topological orderings of the vertices of the graph is _________.
GATE CSE 2015 Set 1Q45MCQ2 marksMediumLet $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…
GATE CSE 2014 Set 1Q3MCQ1 markEasyLet $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$ ?
GATE CSE 2014 Set 1Q11MCQ1 markEasyLet $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?
GATE CSE 2014 Set 1Q13MCQ1 markEasyDiagramConsider the directed graph given below. Which one of the following is TRUE?
GATE CSE 2014 Set 2Q14MCQ1 markEasyConsider 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 computing
GATE CSE 2014 Set 3Q13NAT1 markMediumDiagramSuppose 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 _______.

Topic guide

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.

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
common · MSQ · 2 marks · 2026, 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
common · mixed · 1.5 marks · 2025, 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
common · mixed · 1 marks · 2021, 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)
common · MSQ · 2 marks · 2026, 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
occasional · mixed · 1 marks · 2026, 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.

Graph Traversals

16 Qs · since 2014 · 24 marks · 1 marks/paperStandard yield

Take topic test

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… Guide

Type

Topic guide

What does GATE test in Graph Traversals?

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
common · MSQ · 2 marks · 2026, 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
common · mixed · 1.5 marks · 2025, 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
common · mixed · 1 marks · 2021, 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)
common · MSQ · 2 marks · 2026, 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
occasional · mixed · 1 marks · 2026, 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