An 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? A) Root of T can never be an articulation point in G. B) Root of T is an articulation point in G if and only if it has 2 or more children. C) A leaf of T can be an articulation point in G. D) If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Official answer: B) Root of T is an articulation point in G if and only if it has 2 or more children.. Explanation: Let G be a connected undirected graph and T be its DFS tree: - Option A is incorrect and Option B is correct: By the standard DFS articulation point theorem, the root of a DFS tree T is an articulation point in G if and only if it has two or more children in T. If it has only one child, removing it leaves the rest of the graph connected because all other vertices are descendants of that single child and are connected via tree edges and back edges. - Option C is incorrect: A leaf vertex in a DFS tree has no descendants. Removing a leaf vertex cannot disconnect any remaining vertices in G because all other vertices remain connected via the tree edges of T. Hence, a leaf can never be an articulation point. - Option D is incorrect: If u is an articulation point, it disconnects at least one subtree of its descendants from the rest of the graph. However, it is not necessarily true that *all* descendants y are disconnected from an ancestor x, because another descendant y' might have a back edge to an ancestor of u, providing a path between x and y' that does not pass through u. Therefore, only B is correct.

A) Root of T can never be an articulation point in G.

B) Root of T is an articulation point in G if and only if it has 2 or more children.

C) A leaf of T can be an articulation point in G.

D) If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Algorithms · Graph Traversals

Official IIT answer key · IIT Bombay · Audited Aug 2026

Take topic test

GATE CSE 2021 Set 1 Q41 · MSQ · 2 marks

An $\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?

Select one or more options

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests 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.

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

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

Algorithms · Graph Traversals

Official IIT answer key · IIT Bombay · Audited Aug 2026

Take topic test

GATE CSE 2021 Set 1 Q41 · MSQ · 2 marks

An $\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?

Select one or more options

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

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

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 1

More on Graph Traversals

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 1

More on Graph Traversals

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 1

More on Graph Traversals

Share this solution

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2021 Set 1

More on Graph Traversals

Share this solution