The GATE Grind

GATE 2021 CS – Question 51

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple select

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?

  1. Root of $T$ can never be an articulation point in $G$.
  2. Root of $T$ is an articulation point in $G$ if and only if it has 2 or more children.
  3. A leaf of $T$ can be an articulation point in $G$.
  4. 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$.

Practise this question in The GATE Grind →

Show answer and explanation

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

Explanation

The DFS root is an articulation point iff it has at least two children. A leaf has no descendants, so removing it never disconnects the graph. Statement D is false because a back edge can bypass u.