Graph Theory37 sections · 1633 units
Open in Course

Articulation Point: Root Case

(Root with multiple children)

If the DFS root has 2\geq 2 children in the DFS tree, it is an articulation point. Why?

Each child represents a separate subtree. These subtrees are only connected through the root. Remove the root, and they become disconnected components. If the root has only 11 child, it is not an articulation point. The entire graph is one connected tree below it, and removing the root leaves that tree (or a single vertex if n=2n=2).