Cut Vertices, Bridges, and Biconnectivity

The fragile point in a connected network

Picture a city where every junction can reach every other. Now imagine one junction collapses. In a well-built city the traffic just reroutes; in a fragile one, a whole neighbourhood is suddenly cut off, marooned from the rest. That single junction whose removal disconnects the network is what we are hunting in this guide. In graph language: an articulation point (or cut vertex) is a vertex whose deletion — along with all its edges — increases the number of connected components of the graph. The companion notion is a bridge: an edge whose deletion does the same. Both are the network's single points of failure, and finding them matters wherever resilience matters: power grids, road maps, communication backbones, supply chains.

The naive method is honest but slow: for each of the V vertices, delete it, re-run a search, and check whether the graph fell apart. Each test costs a full traversal of O(V + E), so the whole thing is O(V * (V + E)) — fine for a tiny graph, hopeless for a large one. The beautiful result of this guide is that a single depth-first search finds every articulation point and every bridge in one pass, in the same O(V + E) it took just to walk the graph once. We get the fragility map for free, riding along on a search we already knew how to run.

The DFS tree is the secret weapon

The whole trick rests on a fact you met two guides ago. When depth-first search explores an undirected graph, it carves out a DFS tree, and the edge classification becomes startlingly simple: every edge is either a tree edge (used to discover a new vertex) or a back edge that climbs from a vertex up to one of its own ancestors in the tree. Crucially, an undirected DFS produces no cross edges at all. Why? If there were an edge between two vertices in different branches, whichever one DFS reached first would have walked across that edge and made the other its descendant — so they could never have ended up in separate branches. That single guarantee — only tree edges and back edges, never a sideways jump — is what makes cut vertices detectable from the tree alone.

Here is the intuition that turns the tree into an answer. Think of a vertex u and the subtree hanging beneath one of its children. For that subtree to survive u being deleted, it must have some other way out — some back edge that climbs from inside the subtree to an ancestor strictly above u, sidestepping u entirely. If even one child's subtree has no such escape route, then u is the only path connecting that subtree to the rest of the graph, and deleting u strands it. That is precisely what makes u an articulation point. So the question "is u a cut vertex?" reduces to "can each of u's children's subtrees reach above u without going through u?" — and to answer that, we need a number.

Two numbers per vertex: discovery time and low-link

Give every vertex a discovery time disc[v]: a counter, starting at 1, that ticks up by one each time DFS first visits a vertex. So disc tells you the order DFS reached things — an ancestor always has a smaller disc than its descendants. Now define the star of the show, the low-link value low[v]: the smallest discovery time reachable from v by going down through any number of tree edges in v's subtree and then taking at most one back edge. In plain words, low[v] is the highest point (smallest disc) that the whole subtree rooted at v can climb back to using the edges available inside it. If low[v] is small, that subtree has a ladder reaching far up the tree; if low[v] equals disc[v], the subtree can reach no higher than v itself.

DFS(u, parent):
  disc[u] = low[u] = ++timer
  for each neighbour v of u:
      if v == parent:  continue          # don't bounce back on the tree edge
      if v not visited:                  # tree edge: recurse, then absorb child
          DFS(v, u)
          low[u] = min(low[u], low[v])
          # bridge:  low[v] >  disc[u]
          # cut pt:  low[v] >= disc[u]   (non-root u);  root needs >=2 children
      else:                              # back edge to an ancestor
          low[u] = min(low[u], disc[v])

Computing low[v] is wonderfully local. When DFS finishes a vertex v, low[v] is just the minimum of three things: its own disc[v]; the disc of any ancestor it can reach by a direct back edge; and the low value of each of its tree children (because anything a child's subtree can reach, v can reach too, by going down into that child first). So low bubbles upward as the recursion returns — each child hands its low value to its parent, who takes the smallest. This is the same upward-flowing bookkeeping that powers Tarjan's algorithm for strongly connected components from the previous guide; the low-link idea is one tool wearing two hats, here on undirected graphs instead of directed ones.

Reading off bridges and cut vertices

With disc and low in hand, the two conditions are crisp. Consider a tree edge from u down to its child v. The edge (u, v) is a bridge exactly when low[v] > disc[u]. Read that literally: the highest point v's whole subtree can reach is strictly below u, so the only link tying that subtree to the world above is this one edge — cut it and the subtree falls off. The condition for u being an articulation point is almost identical but with >=: a non-root u is a cut vertex when some child v has low[v] >= disc[u], meaning v's subtree cannot climb above u (it can reach u, but no higher), so removing u severs it.

The DFS root needs its own special rule, and it is easy to see why. The root has no ancestor, so the low/disc comparison above is meaningless for it. Instead: the root is an articulation point exactly when it has two or more tree children. One child means the root sat at the end of a chain and removing it leaves the rest connected; two children means DFS had to restart into a second branch it could not reach from the first — so those branches are joined only through the root, and deleting the root splits them. Handle the root by counting its tree children; handle every other vertex by the low[v] >= disc[u] test.

Biconnectivity: networks with no single point of failure

Flip the whole picture around and you get a design goal rather than a vulnerability. A connected graph is biconnected when it has no articulation points at all — no single vertex whose loss disconnects it. Equivalently, and this is the lovely characterization, a graph is biconnected when between every pair of vertices there are at least two vertex-disjoint paths: two routes that share no intermediate junction. That is exactly the redundancy an engineer wants. Any one node can fail and traffic still finds a way, because there was always a second independent path waiting.

1. Run one DFS, assigning disc and low to every vertex as the recursion descends and returns.
2. As each tree edge (u, v) finishes, push it onto a stack of edges so far unassigned to a block.
3. When you hit the articulation condition low[v] >= disc[u], pop edges off the stack down to (u, v): those popped edges form one biconnected block (a maximal biconnected piece).
4. Articulation points are exactly the vertices shared by two or more such blocks — the hinges where the network's redundant pieces are stitched together.

A small honesty check, because it is easy to over-promise. Biconnectivity is about vertex failure — surviving the loss of any one node. The parallel idea for edge failure (surviving the loss of any one link) is a graph with no bridges, a distinct property; a graph can have no bridges yet still have a cut vertex, and vice versa. And the whole low-link machinery here is built for undirected graphs, leaning on the no-cross-edges guarantee; the directed-graph cousins of these questions (strong connectivity, SCC decomposition) need the directed version of the same idea, which is why they earned their own guide. Same elegant O(V + E) cost, same disc/low bookkeeping — but you must apply it to the right kind of graph.

Why it is correct, and what it costs

The correctness rests squarely on the no-cross-edge property. Because an undirected DFS produces only tree edges and back edges, every path that escapes a subtree without using u must do so via a back edge from inside the subtree to an ancestor of u — there is simply no other kind of edge available. That is why low[v], which captures precisely "the highest ancestor any back edge in v's subtree can reach," is a complete summary of the subtree's escape options. Nothing is missed, because cross edges (which could have offered a sneaky sideways exit) do not exist in this setting. The test low[v] >= disc[u] is therefore not a heuristic that usually works; it is exactly equivalent to "v's subtree has no exit above u," which is the literal definition of u cutting v off.

The running time is the headline payoff. We do exactly one DFS, touching every vertex once and examining each edge a constant number of times, so the total is O(V + E) — the same bound BFS and DFS earned in the earlier guides, inherited from the adjacency-list traversal. Compare that to the naive delete-and-retest approach at O(V * (V + E)): on a sparse graph of a million vertices, the difference is roughly a million-fold. Be honest, though, about what O(V + E) does and does not promise. It is asymptotic, so the hidden constants of recursion and stack bookkeeping mean that for a handful of tiny graphs the naive scan might not feel slower; the win is in scaling, and that win is overwhelming exactly where it matters — on the large networks whose resilience you actually need to audit.