Skip to content
GATEiit

GATE CSE 2021 Set 1 Q51: Articulation points and the DFS tree

Question

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

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: B (official GATE 2021 final answer key)

Concept used: An undirected DFS has no cross edges, so the root's subtrees are joined only through the root; removing a leaf leaves the tree connected.

First step: For (D), picture an articulation point uu with two child subtrees, one of which has a back edge above uu.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 1 questions →