An articulation point in a connected graph is a vertex such that removing the…
2021
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?
Answer: B. Root of T is an articulation point in G if and only if it has 2 or more children. — Answer: The root of the DFS tree is an articulation point exactly when it has two or more children. If the root has two or more children, removing the root…
- 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.
Attempted by 165 students.
Show answer & explanation
Correct answer: B
Answer: The root of the DFS tree is an articulation point exactly when it has two or more children.
If the root has two or more children, removing the root separates those child subtrees from each other, producing at least two connected components.
If the root has fewer than two children (zero or one), removing it leaves at most one remaining connected part, so the graph stays connected.
Related fact for non-root vertices: a non-root vertex u is an articulation point iff it has a child v with low[v] >= disc[u]. Because leaves have no children, they cannot be articulation points.
A video solution is available for this question — log in and enroll to watch it.