Bridges & Articulation Points

We have seen depth-first search lay a tree over a graph, and we used that tree to direct edges, find cycles, and decompose a digraph into strongly connected components. This lesson turns the same machinery on a different question, one that matters whenever a graph models a network. Which parts of it are fragile? If a single fiber link is cut or a single router fails, does the network split into pieces that can no longer reach one another? These single points of failure have names.

A graph with no bridges is 2-edge-connected: you must cut at least two edges to disconnect it, so every pair of vertices is joined by two edge-disjoint paths. A graph with no articulation points (and at least three vertices) is 2-vertex-connected, or biconnected: two vertex-disjoint paths between every pair.¹ The maximal biconnected subgraphs are the biconnected components; bridges and cut vertices are exactly the seams where they meet. So the question where is my network fragile? is the question find the cut edges and cut vertices, and the surprise is that one DFS answers it.

The DFS-tree view

Run DFS from any vertex of a connected, undirected graph. Classify each edge by when DFS first traverses it. The decisive structural fact is that only two kinds survive.

This is what makes undirected connectivity tractable: the only way to leave a DFS subtree is a back edge climbing to an ancestor. Bridges and cut vertices are both about whether such an escape exists. To detect it we time the search and track how high each subtree can climb.

In words, $low[u]$ is the smallest discovery time reachable from $u$'s DFS subtree using any number of tree edges (downward) plus at most one back edge (the final hop up). It measures the highest ancestor the subtree rooted at $u$ can reach without going through $u$'s parent. Both quantities are computed in the same recursion: set $disc[u]=low[u]$ on entry, then relax $low[u]$ against each child's finished $low$ and each back edge's target $disc$.

In the figure each node is labeled $disc/low$. The back edge $C\to A$ pulls $low[C]=low[B]=1$, so the subtrees of $B$ and $C$ can all climb back above their parents: none of $A-B$, $B-C$ is a bridge. But $D$ is a dead end, $low[D]=disc[D]=4$, nothing in $D$'s subtree reaches above $C$, so cutting $C-D$ strands $D$. The edge $A-E$ is a bridge too, since $E$'s only escape, the back edge $F\to E$, stays inside $E$'s own subtree.

The bridge criterion

Why. Removing the tree edge $(u,v)$ separates $v$'s subtree from the rest of the tree. The only edges that could still bind the subtree to the upper graph are back edges out of it. A back edge from inside $v$'s subtree lands on some ancestor $w$ with $disc[w]=low[v]$ (its lowest reach). If $low[v]\le disc[u]$ that ancestor is $u$ or higher, so an alternative route exists and $(u,v)$ is not a bridge. If $low[v]>disc[u]$ no back edge escapes above $u$ through any vertex other than via the edge $(u,v)$ itself, so cutting it disconnects the subtree: $(u,v)$ is a bridge. Note the strict inequality: reaching $u$ itself ($low[v]=disc[u]$) is enough to save the edge. $\square$

The articulation criterion

Cut vertices need one more case, because removing $u$ deletes all of $u$'s incident edges at once, including the tree edges to each child.

Why the root case. The root has no ancestors, so back edges cannot help. If it has two or more children, those child-subtrees were discovered separately and the only edges joining them ran through the root (cross edges don't exist), so deleting the root splits them. One child means the root is just a leaf-side endpoint and removing it leaves the rest connected.

Why the non-root case. For a non-root $u$, deleting $u$ severs child $v$'s subtree from $u$. That subtree stays attached to the rest of the graph only if some back edge climbs strictly above $u$, i.e. $low[v]<disc[u]$. If instead $low[v]\ge disc[u]$, every escape from $v$'s subtree reaches no higher than $u$ itself, so removing $u$ isolates that subtree and $u$ is a cut vertex. The contrast with the bridge test is exactly the boundary case: a back edge to $u$ ($low[v]=disc[u]$) saves the edge $(u,v)$ but does not save the vertex$u$, since deleting $u$ destroys that back edge's endpoint too. Hence $>$ for bridges, $\ge$ for cut vertices. $\square$

Here the back edge $X\to U$ gives $low[X]=disc[U]=2$. The subtree of $X$ can climb to $U$ but no higher, so $low[X]\ge disc[U]$ holds and $U$ is a cut vertex: deleting it strands $X$ and $Y$ from $R$. Yet the edge $U-X$ is not a bridge, since $low[X]=disc[U]$ is not strictly greater. The same local data, two thresholds apart, distinguishes fragile edges from fragile vertices.

One DFS finds them all

Both criteria read off $disc$ and $low$, so a single recursion computes everything. The one subtlety is the parent edge: in an undirected graph the edge back to the parent must not be mistaken for a back edge that lowers $low$. Guarding by parent vertex is correct only when there are no multi-edges (two distinct edges between the same pair); with multi-edges, a second $u$–parent edge is a genuine back edge and the second copy must be allowed to lower $low$. The reliable fix is to track the parent edge id rather than the parent vertex.

Each vertex is discovered once and each edge is examined a constant number of times (twice over the whole run, once from each endpoint), so the search is $\Theta (V+E)$, asymptotically free on top of the DFS we were already running. The outer loop over $s$ makes it work on disconnected graphs as well: it finds the bridges and cut vertices of every component. The same low-link bookkeeping, with a stack of edges, also peels off the biconnected components directly (pop the stack down to $(u,v)$ whenever $low[v]\ge disc[u]$), which is Tarjan's original formulation.²³

Takeaways

• A bridge (cut edge) and an articulation point (cut vertex) are the single points of failure of a network: removing one increases the component count. Their absence is 2-edge-connectivity and 2-vertex-connectivity (biconnectivity); cut edges and vertices are the seams between biconnected components.
• DFS on an undirected graph produces only tree edges and back edges, with no cross or forward edges, so the only way out of a subtree is a back edge to an ancestor.
• The low-link $low[u]$ is the smallest discovery time reachable from $u$'s subtree via tree edges plus at most one back edge; compute it alongside $disc[u]$ in one recursion.
• Bridge criterion: tree edge $(u,v)$ is a bridge $\leftrightarrow low[v]>disc[u]$. Articulation criterion: a non-root $u$ is a cut vertex $\leftrightarrow$ some child has $low[v]\ge disc[u]$; the root is a cut vertex $\leftrightarrow$ it has $\ge 2$ children. The strict-vs-nonstrict gap ($>$ vs $\ge$) is the whole distinction.
• A single $O(V+E)$ DFS reports all bridges and cut vertices (and biconnected components). Guard the parent edge by id, not the parent vertex, to stay correct under multi-edges.