Graph Theory37 sections · 1633 units
Open in Course

Articulation Point: Non-Root Case

(Child cannot bypass parent)

For a non-root vertex uu with child vv in the DFS tree: If low[v] >= disc[u], then uu is an articulation point. Why? low[v] >= disc[u] means the subtree rooted at vv cannot reach any vertex discovered before uu.

The subtree can reach uu (when low[v] = disc[u]) or only later vertices (when low[v] > disc[u]). Either way, uu is the gateway. Remove uu, and the subtree disconnects.