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?
Root of $T$ can never be an articulation point in $G$.
Root of $T$ is an articulation point in $G$ if and only if it has 2 or more children.
A leaf of $T$ can be an articulation point in $G$.
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$.
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.
More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions
GATE 2020 CS Q41– Let G=(V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G…
GATE 2020 CS Q50– Let G=(V,E) be a directed, weighted graph with weight function w:ER. For some function…
GATE 2020 CS Q59– Consider a graph G=(V,E), where V=\v 1,v 2,,v 100\, E=\(v i,v j) 1 i<j 100\, and weight of…
GATE 2019 CS Q48– Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning…
GATE 2018 CS Q40– Let G be a simple undirected graph. Let T D be a depth first search tree of G. Let T B be…
GATE 2018 CS Q57– Consider the following undirected graph G (the edge weights are shown in the figure, with…