GateAI
Graph Traversals

GATE CSE 2021 Set 1 · Q41

MSQ2 marksMedium

Time

An articulation point\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 TT be a DFS tree obtained by doing DFS in a connected undirected graph GG. Which of the following options is/are correct?

Select all that applyOne or more correct

Pick every correct option

Solution

Step-by-step verified solution

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

Graph Traversals

Let GG be a connected undirected graph and TT 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 TT is an articulation point in GG if and only if it has two or more children in TT. 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 GG because all other vertices remain connected via the tree edges of TT. Hence, a leaf can never be an articulation point.

  • Option D is incorrect: If uu 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 yy are disconnected from an ancestor xx, because another descendant y′y^{\prime} might have a back edge to an ancestor of uu, providing a path between xx and y′y^{\prime} that does not pass through uu.

Therefore, only B is correct.

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 Q41 of the GATE CSE 2021 Set 1 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 1.

How GATE tests Graph Traversals

More from GATE CSE 2021 Set 1

Share this solution

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

GateAI solution cardGATE CSE 2021 Set 1 · Q41 · MSQ

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?

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.