---
title: Bridges & Articulation Points
module: Graphs
moduleNumber: 6
lessonNumber: 10
order: 610
summary: |
  A **bridge** is an edge whose removal disconnects the graph; an **articulation
  point** is a vertex whose removal does. Both are single points of failure in a
  network. A single depth-first search computes discovery times and **low-links**,
  and two local criteria — $low[v] > disc[u]$ for bridges, $low[v] \ge disc[u]$
  for cut vertices — find them all in $O(V+E)$.
topics: [Graphs]
sources:
  - book: CLRS
    ref: "Ch. 22 — Elementary Graph Algorithms (DFS, problems on connectivity)"
  - book: Skiena
    ref: "§5 — Graph Traversal (connectivity, articulation vertices)"
  - book: Erickson
    ref: "Ch. 6 — Depth-First Search"
practice:
  - title: 'Critical Connections in a Network'
    slug: critical-connections-in-a-network
    difficulty: Hard
  - title: 'Minimize Malware Spread'
    slug: minimize-malware-spread
    difficulty: Hard
  - title: 'Number of Operations to Make Network Connected'
    slug: number-of-operations-to-make-network-connected
    difficulty: Medium
---

We have seen [depth-first search](/algorithms/graphs/representations-and-traversal)
lay a tree over a graph, and we used that tree to
direct edges, find cycles, and decompose a digraph into [strongly connected
components](/algorithms/graphs/topological-sort-and-scc). 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, the network may split into
pieces that can no longer reach one another. These single points of failure have
names.

> **Definition.** In a connected undirected graph $G$, a **bridge** (or _cut
> edge_) is an edge whose removal increases the number of connected components.
> An **articulation point** (or _cut vertex_) is a vertex whose removal, together
> with its incident edges, increases the number of connected components.

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.[^skiena-conn] The maximal biconnected subgraphs are the **biconnected
components**; bridges and cut vertices are the seams where they meet. So
the question "where is my network fragile?" is the question "find the cut edges
and cut vertices," and one DFS answers it.

$$
% caption: 2-edge-connected (left, every edge on a cycle) vs a graph with a bridge (right,
%          $u\!-\!v$ cut)
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % left: 4-cycle, 2-edge-connected
  \node (a) at (0,1.4) {$a$};
  \node (b) at (1.4,1.4) {$b$};
  \node (c) at (1.4,0) {$c$};
  \node (d) at (0,0) {$d$};
  \draw (a)--(b)--(c)--(d)--(a);
  \node[draw=none, font=\footnotesize] at (0.7,-0.8) {no bridge};
  % right: two triangles joined by a single bridge edge
  \node (u) at (4.0,0.7) {$u$};
  \node (v) at (5.6,0.7) {$v$};
  \node (p) at (3.2,1.7) {};
  \node (q) at (3.2,-0.3) {};
  \node (r) at (6.4,1.7) {};
  \node (t) at (6.4,-0.3) {};
  \draw (u)--(p)--(q)--(u);
  \draw (v)--(r)--(t)--(v);
  \draw[acc, very thick] (u)--(v);
  \node[draw=none, font=\footnotesize, text=acc] at (4.8,-0.8) {bridge u-v};
\end{tikzpicture}
$$

## 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.

> **Lemma (no cross edges).** A depth-first search of an undirected graph produces
> only **tree edges** and **back edges**. There are no forward or cross edges.

> **Proof sketch.** Consider any edge $\{u,v\}$, and say DFS visits $u$ first. While
> $u$ is on the recursion stack (gray), the edge $\{u,v\}$ has not yet been used in
> the direction $u \to v$, so $v$ is reachable from $u$ through this edge and will
> become a descendant of $u$ in the DFS tree before $u$ finishes. Thus when we do
> traverse $\{u,v\}$ it connects an ancestor and a descendant: it is either a tree
> edge (if $v$ was undiscovered) or a back edge (if $v$ is an ancestor still on the
> stack). A cross or forward edge would require $v$ to be a non-ancestor relative
> already finished — impossible, since that relative would itself have explored
> $\{u,v\}$ first. $\qed$

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.

$$
% caption: undirected DFS yields only tree edges (solid) and back edges (dashed) — no
%          cross or forward edges
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  level distance=12mm, sibling distance=18mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (a) {$a$}
    child {node (b) {$b$}
      child {node (c) {$c$}}
      child {node (d) {$d$}}
    };
  \draw[acc, dashed, thick] (c) to[bend left=55] (a);
  % tree-edge callout: leader to the solid b--d edge (right, clear of the back edge)
  \node[draw=none, font=\footnotesize] (tlbl) at (2.6,-1.6) {tree edge};
  \draw[thin] (tlbl.west) -- (0.55,-1.85);
  % back-edge callout: leader to the blue dashed curve (left)
  \node[draw=none, font=\footnotesize, text=acc] (blbl) at (-2.7,-1.15) {back edge};
  \draw[thin, acc] (blbl.east) -- (-1.38,-1.17);
\end{tikzpicture}
$$

> **Definition.** Let $disc[u]$ be the **discovery time** of $u$ (a counter
> incremented at each first visit). Define the **low-link**
> $$
> low[u] = \min\parens{\{disc[u]\} \cup \{\,low[c] : c \text{ a tree-child of } u\,\}
>   \cup \{\,disc[w] : \{u,w\} \text{ a back edge}\,\}}.
> $$

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$.

::impl{algo="dfs_lowlink"}

$$
% caption: DFS tree (solid = tree edge, dashed = back edge); bridge
%          $\iff low[v] > disc[u]$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=1pt, font=\small},
  level distance=14mm, sibling distance=22mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (a) {$A$}
    child {node (b) {$B$}
      child {node (c) {$C$}
        child {node (d) {$D$}}
      }
    };
  \node (e) [right=34mm of a] {$E$}
    child {node (f) {$F$}};
  % tree edge A-E: also a bridge (E's subtree never climbs above E)
  \draw[acc, very thick] (a) -- (e);
  % back edges (dashed)
  \draw[dashed] (c) to[bend left=45] (a);
  \draw[dashed] (f) to[bend right=35] (e);
  % the bridge C-D highlighted
  \draw[acc, very thick] (c) -- (d);
  % disc/low labels
  \node[draw=none, above=1mm of a, font=\scriptsize] {1/1};
  \node[draw=none, right=1mm of b, font=\scriptsize] {2/1};
  \node[draw=none, right=1mm of c, font=\scriptsize] {3/1};
  \node[draw=none, right=1mm of d, font=\scriptsize, text=acc] {4/4};
  \node[draw=none, above=1mm of e, font=\scriptsize] {5/5};
  \node[draw=none, right=1mm of f, font=\scriptsize] {6/5};
\end{tikzpicture}
$$

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

The criterion $low[v] > disc[u]$ is a decision test on a single edge — _is this a
bridge?_ — and the iff is its two-sided correctness in the sense of
[the foundations](/algorithms/foundations/what-is-an-algorithm). The forward
direction ($low[v] > disc[u]$ implies the edge really is a bridge) is its
**soundness**: the test never flags a safe edge. The reverse (a true bridge always
satisfies $low[v] > disc[u]$, since otherwise a back edge offers an alternative
route) is its **completeness**: no bridge is missed.

> **Theorem (bridge).** Let $(u,v)$ be a tree edge with $v$ the child. Then
> $(u,v)$ is a bridge $\iff low[v] > disc[u]$.

> **Proof.** 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. The inequality is strict for a reason: reaching $u$
> itself ($low[v]=disc[u]$) is enough to save the edge. $\qed$

## 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.

> **Theorem (articulation point).**
> - The DFS **root** is an articulation point $\iff$ it has $\ge 2$ tree children.
> - A **non-root** vertex $u$ is an articulation point $\iff$ $u$ has some tree
>   child $v$ with $low[v] \ge disc[u]$.

> **Proof.** _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.
>
> _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 comes down to 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. $\qed$

$$
% caption: cut vertex $\iff low[child] \ge disc[u]$ (or root with $\ge 2$ children)
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=9mm, inner sep=1pt, font=\small},
  level distance=14mm, sibling distance=24mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (r) {$R$}
    child {node (u) {$U$}
      child {node (x) {$X$}
        child {node (y) {$Y$}}
      }
    };
  % cut vertex U highlighted (empty thick-border node on top — label drawn once)
  \node[draw=acc, very thick, minimum size=9mm, inner sep=1pt] at (u) {};
  % back edge X -> U (reaches U but not above)
  \draw[dashed] (x) to[bend left=45] (u);
  % bracket-free annotation of the stranded subtree
  \node[draw=none, right=10mm of x, font=\scriptsize, text=acc, align=left]
    {subtree of $X$:\\$low[X]=disc[U]$};
  \node[draw=none, left=1mm of r, font=\scriptsize] {1/1};
  \node[draw=none, left=1mm of u, font=\scriptsize, text=acc] {2/2};
  \node[draw=none, left=1mm of x, font=\scriptsize] {3/2};
  \node[draw=none, left=1mm of y, font=\scriptsize] {4/4};
\end{tikzpicture}
$$

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.

```algorithm
caption: $\textsc{Bridges-AP}(G)$ — find all bridges and articulation points in $O(V+E)$
$timer \gets 0$;\ \ $disc[\,\cdot\,] \gets 0$ (0 = unvisited)
for each vertex $s$ in $V$ do
  if $disc[s] = 0$ then $\textsc{Dfs}(s,\ \text{nil})$  // nil = no parent edge

procedure $\textsc{Dfs}(u,\ pe)$:   // $pe$ = id of edge to parent
  $timer \gets timer + 1$
  $disc[u] \gets low[u] \gets timer$
  $children \gets 0$
  for each incident edge $e = \{u,w\}$ do
    if $e = pe$ then continue            // skip arrival edge
    if $disc[w] = 0$ then                // tree edge
      $children \gets children + 1$
      $\textsc{Dfs}(w,\ e)$
      $low[u] \gets \min(low[u],\ low[w])$
      if $low[w] > disc[u]$ then report bridge $\{u,w\}$
      if $pe \ne \text{nil}$ and $low[w] \ge disc[u]$ then mark $u$ articulation
    else                                 // back edge
      $low[u] \gets \min(low[u],\ disc[w])$
  if $pe = \text{nil}$ and $children \ge 2$ then mark $u$ articulation
```

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](/algorithms/foundations/asymptotic-analysis) 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.[^clrs-dfs][^erickson-dfs]

> **Intuition.** $low[u]$ is the highest rung of the ancestor ladder that $u$'s
> subtree can reach. A _tree edge_ is a bridge when the child cannot reach any
> rung above its parent ($>$); a _vertex_ is a cut vertex when some child cannot
> reach any rung strictly above $u$ ($\ge$, because deleting $u$ also removes the
> rung at $u$). One ladder, two thresholds.

## A complete trace

Here is the whole computation, step by step, on a seven-vertex graph built from
two triangles joined by a chain: triangle $a, b, c$, bridge $c\!-\!d$, triangle
$d, e, f$, bridge $f\!-\!g$. Deleting $c$, $d$, or $f$ splits the graph, so
those three are its cut vertices.

$$
% caption: The input graph: triangles $\{a,b,c\}$ and $\{d,e,f\}$ joined by the
%          bridge $c\!-\!d$, with a pendant bridge $f\!-\!g$. Cut vertices $c$,
%          $d$, $f$ are ringed.
\begin{tikzpicture}[>=stealth, font=\small,
  V/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[V] (a) at (0,2.2) {$a$};
  \node[V] (b) at (1.6,2.2) {$b$};
  \node[V] (c) at (0.8,1.0) {$c$};
  \node[V] (d) at (2.4,0.2) {$d$};
  \node[V] (e) at (4.0,1.0) {$e$};
  \node[V] (f) at (4.2,-0.6) {$f$};
  \node[V] (g) at (5.8,-0.6) {$g$};
  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw (c) -- (a);
  \draw[acc, very thick] (c) -- (d);
  \draw (d) -- (e);
  \draw (e) -- (f);
  \draw (f) -- (d);
  \draw[acc, very thick] (f) -- (g);
  \node[draw=acc, thick, circle, minimum size=8.6mm, inner sep=0pt] at (c) {};
  \node[draw=acc, thick, circle, minimum size=8.6mm, inner sep=0pt] at (d) {};
  \node[draw=acc, thick, circle, minimum size=8.6mm, inner sep=0pt] at (f) {};
  \node[draw=none, font=\footnotesize, text=acc] at (0.9,0.15) {bridge};
  \node[draw=none, font=\footnotesize, text=acc] at (5.0,-1.25) {bridge};
\end{tikzpicture}
$$

Start DFS at $a$ with alphabetical adjacency lists. The recursion discovers the
chain $a, b, c, d, e, f, g$ (each vertex's first unvisited neighbor happens to
be the next letter), and the interesting work happens on the way back up:

| step | event                              | effect                                                         |
| ---- | ---------------------------------- | -------------------------------------------------------------- |
| 1    | discover $a$                       | $disc[a] = low[a] = 1$                                          |
| 2    | discover $b$ via tree edge $a\!-\!b$ | $disc[b] = low[b] = 2$                                        |
| 3    | discover $c$ via tree edge $b\!-\!c$ | $disc[c] = low[c] = 3$                                        |
| 4    | $c$ sees $a$: back edge            | $low[c] = \min(3, disc[a]) = 1$                                 |
| 5    | discover $d$ via tree edge $c\!-\!d$ | $disc[d] = low[d] = 4$                                        |
| 6    | discover $e$ via tree edge $d\!-\!e$ | $disc[e] = low[e] = 5$                                        |
| 7    | discover $f$ via tree edge $e\!-\!f$ | $disc[f] = low[f] = 6$                                        |
| 8    | $f$ sees $d$: back edge            | $low[f] = \min(6, disc[d]) = 4$                                 |
| 9    | discover $g$ via tree edge $f\!-\!g$ | $disc[g] = low[g] = 7$; $g$ has no other neighbor, returns    |
| 10   | $g$ returns to $f$                 | $low[f] = \min(4, 7) = 4$; $low[g] = 7 > disc[f] = 6$: **bridge** $f\!-\!g$; $low[g] \ge disc[f]$: **$f$ is a cut vertex** |
| 11   | $f$ returns to $e$                 | $low[e] = \min(5, 4) = 4$; $low[f] = 4 \not> disc[e] = 5$: no bridge, no cut |
| 12   | $e$ returns to $d$                 | $low[d] = \min(4, 4) = 4$; $low[e] = 4 \ge disc[d] = 4$: **$d$ is a cut vertex** (but $4 \not> 4$: $d\!-\!e$ is no bridge) |
| 13   | $d$ sees $f$: second view of edge $d\!-\!f$ | $low[d] = \min(4, disc[f]) = 4$, no change                |
| 14   | $d$ returns to $c$                 | $low[c] = \min(1, 4) = 1$; $low[d] = 4 > disc[c] = 3$: **bridge** $c\!-\!d$; $low[d] \ge disc[c]$: **$c$ is a cut vertex** |
| 15   | $c$ returns to $b$                 | $low[b] = \min(2, 1) = 1$; $low[c] = 1 \not> disc[b] = 2$: nothing |
| 16   | $b$ returns to $a$                 | $low[a] = \min(1, 1) = 1$; root $a$ has $1$ tree child: **not** a cut vertex |
| 17   | $a$ sees $c$: second view of edge $a\!-\!c$ | $low[a] = \min(1, disc[c]) = 1$, no change                |

Steps 13 and 17 show a quiet feature of undirected DFS: every non-tree edge is
examined twice, once from each endpoint. The view from the _ancestor_ side
($d$ looking at $f$, $a$ looking at $c$) relaxes against a _larger_ discovery
time and never changes anything; only the view from the descendant side (steps
4 and 8) matters. Both sightings are harmless as long as neither is mistaken
for the parent edge.

The final state, drawn on the DFS tree — which for this graph is a single
chain — with each vertex labeled $disc/low$:

$$
% caption: The DFS tree of the trace (a chain), back edges dashed, each vertex
%          labeled $disc/low$. Bridges in blue: exactly the tree edges with
%          $low[\text{child}] > disc[\text{parent}]$; cut vertices $c$, $d$,
%          $f$ ringed.
\begin{tikzpicture}[>=stealth, font=\small,
  V/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[V] (a) at (0,0) {$a$};
  \node[V] (b) at (1.3,0) {$b$};
  \node[V] (c) at (2.6,0) {$c$};
  \node[V] (d) at (3.9,0) {$d$};
  \node[V] (e) at (5.2,0) {$e$};
  \node[V] (f) at (6.5,0) {$f$};
  \node[V] (g) at (7.8,0) {$g$};
  \draw (a) -- (b);
  \draw (b) -- (c);
  \draw[acc, very thick] (c) -- (d);
  \draw (d) -- (e);
  \draw (e) -- (f);
  \draw[acc, very thick] (f) -- (g);
  \draw[->, dashed] (c) to[bend right=42] (a);
  \draw[->, dashed] (f) to[bend right=42] (d);
  \node[draw=acc, thick, circle, minimum size=8.6mm, inner sep=0pt] at (c) {};
  \node[draw=acc, thick, circle, minimum size=8.6mm, inner sep=0pt] at (d) {};
  \node[draw=acc, thick, circle, minimum size=8.6mm, inner sep=0pt] at (f) {};
  \node[draw=none, font=\scriptsize] at (0,-0.75) {1/1};
  \node[draw=none, font=\scriptsize] at (1.3,-0.75) {2/1};
  \node[draw=none, font=\scriptsize] at (2.6,-0.75) {3/1};
  \node[draw=none, font=\scriptsize] at (3.9,-0.75) {4/4};
  \node[draw=none, font=\scriptsize] at (5.2,-0.75) {5/4};
  \node[draw=none, font=\scriptsize] at (6.5,-0.75) {6/4};
  \node[draw=none, font=\scriptsize] at (7.8,-0.75) {7/7};
\end{tikzpicture}
$$

Reading the picture against the two criteria: the back edge $c \to a$ pins
$low$ at $1$ across the first triangle, so nothing in $\{a, b, c\}$ is
separated by removing one edge; the back edge $f \to d$ pins $low$ at $4$
across the second. The only tree edges whose child cannot climb past the
parent are $c\!-\!d$ ($low[d] = 4 > 3$) and $f\!-\!g$ ($low[g] = 7 > 6$) — the
two bridges. And the children $d$, $e$, $g$ certify $c$, $d$, $f$ as cut
vertices via $low[v] \ge disc[u]$, while the root $a$, with a single tree
child, is exempt.

## Common pitfalls

- **The root always passes the non-root test.** Since $disc[root]$ is the
  smallest discovery time in its tree, _every_ child $v$ satisfies
  $low[v] \ge disc[root]$. Apply the non-root rule to the root and it is
  flagged unconditionally. The root must be special-cased by counting tree
  children — and _tree_ children, not neighbors: in a triangle the root has
  degree $2$ but only one tree child (the other neighbor is reached around the
  cycle), and it is correctly not a cut vertex.
- **Skipping the parent by vertex instead of by edge.** With parallel edges,
  "ignore neighbors equal to my parent" skips _both_ copies of a doubled edge,
  so the child looks trapped and the pair is reported as a bridge — but a
  doubled edge is never a bridge, since the twin copy survives any single cut.
  Track the id (or adjacency-list index) of the arrival edge and skip only that
  one; the second copy then acts as a legitimate back edge and lowers $low$.
- **Relaxing back edges with $low[w]$ instead of $disc[w]$.** The definition
  permits at most one back edge per escape route, and the proofs lean on it.
  While $w$ is still gray, $low[w]$ is a moving target, and chaining through it
  can credit $v$ with escape routes that pass through vertices whose deletion
  is under test. Back edges relax against $disc[w]$, tree edges against the
  child's finished $low$.
- **Testing the wrong pair.** The bridge test compares the _child's low_
  against the _parent's disc_: $low[v] > disc[u]$. Both nearby variants fail.
  Comparing $disc[v] > disc[u]$ flags every tree edge, since children are
  always discovered later. Comparing $low[v] > low[u]$ breaks when $u$ has its
  own escape: attach a triangle $u, v, w$ below a vertex $r$, plus a back edge
  from $u$ to $r$'s parent $s$. Then $low[u] = 1 < low[v] = disc[u]$, so
  $low[v] > low[u]$ misreports the cycle edge $u\!-\!v$ as a bridge even
  though $u, v, w$ sit on a common cycle.
- **Recursion depth.** The DFS tree of a path graph is the whole path; on a
  million-vertex chain the recursive version overflows most default call
  stacks. An explicit-stack rewrite must still perform the _post-visit_
  relaxation $low[u] \gets \min(low[u], low[w])$ when a child is popped, which
  takes some care to get right; test it on long chains.

The parallel-edge trap deserves a picture, because the buggy and correct runs
differ on the smallest possible graph:

$$
% caption: Parallel edges $\{u,v\}$: guarding by parent vertex skips both
%          copies and misreports a bridge (left); guarding by the arrival
%          edge's id lets the twin copy act as a back edge, $low[v] =
%          disc[u]$, no bridge (right).
\begin{tikzpicture}[>=stealth, font=\small,
  V/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % left: guard by vertex — both copies skipped, false bridge
  \node[V] (u1) at (0,1.5) {$u$};
  \node[V] (v1) at (0,0) {$v$};
  \draw[acc, very thick] (u1) to[bend right=28] (v1);
  \draw[acc, very thick] (u1) to[bend left=28] (v1);
  \node[draw=none, font=\footnotesize] at (0,2.3) {skip parent vertex};
  \node[draw=none, font=\footnotesize, text=acc] at (0,-0.85) {false bridge};
  \node[draw=none, font=\scriptsize] at (1.05,0.0) {2/2};
  \node[draw=none, font=\scriptsize] at (1.05,1.5) {1/1};
  % right: guard by edge id — twin copy is a back edge
  \node[V] (u2) at (4.6,1.5) {$u$};
  \node[V] (v2) at (4.6,0) {$v$};
  \draw (u2) to[bend right=28] (v2);
  \draw[dashed] (v2) to[bend right=28] (u2);
  \node[draw=none, font=\footnotesize] at (4.6,2.3) {skip parent edge};
  \node[draw=none, font=\footnotesize] at (4.6,-0.85) {no bridge};
  \node[draw=none, font=\scriptsize] at (5.65,0.0) {2/1};
  \node[draw=none, font=\scriptsize] at (5.65,1.5) {1/1};
\end{tikzpicture}
$$

On the left, $v$'s only edges both lead to its parent, both are skipped, and
$low[v]$ stays at $disc[v] = 2 > disc[u] = 1$: the doubled edge is declared a
bridge, wrongly. On the right, only the arrival copy is skipped; the twin is
processed as a back edge (dashed), $low[v]$ drops to $1 = disc[u]$, and the
strict test correctly reports nothing.

## When to reach for this

The low-link machinery answers "what breaks if one element fails," and it
shows up wherever that question does: single points of failure in a computer
or transport network, load-bearing joints in a mesh, and the decomposition of
a graph into biconnected components before running algorithms that assume
2-connectivity. Two contrasts are worth keeping straight. First, bridges and
cut vertices concern _undirected_ connectivity; the analogous directed
question is answered by [strongly connected
components](/algorithms/graphs/topological-sort-and-scc), and Tarjan's SCC
algorithm reuses this same low-link idea with a stack. Second, the criteria
are about single failures only — surviving the loss of any $k$ edges or
vertices is $(k{+}1)$-connectivity, which calls for maximum-flow techniques
rather than one DFS.

::impl{algo="bridges,articulation_points,biconnected_components"}

## Connectivity, statically and dynamically

**The block-cut tree.** Grouping the graph's biconnected components (blocks) and articulation points into a tree — a node per block, a node per cut vertex, an edge whenever a cut vertex lies on a block — gives the **block-cut tree**, a compact map of exactly how the graph can fall apart.[^hopcroft-tarjan] Any two vertices in the same block survive the loss of one vertex; a path between blocks in the tree passes through precisely the cut vertices that would disconnect them. Many "is the graph still connected if I delete $v$" queries become tree lookups after one $O(V+E)$ preprocessing pass. The edge analogue, contracting each 2-edge-connected component, yields the **bridge tree**, in which each tree edge is a bridge of the graph.

**Beyond single failures.** Bridges and cut vertices are the $k = 1$ case of a hierarchy. Surviving _any_ two edge failures is **3-edge-connectivity**; the general question "is the graph $k$-connected" is answered by max-flow (Menger's theorem equates the minimum $s$–$t$ cut with the number of vertex- or edge-disjoint $s$–$t$ paths), and global $k$-edge-connectivity by the Stoer-Wagner minimum-cut algorithm. The single-DFS low-link trick is special to $k = 1$ — it is what makes that one case linear.

**Dynamic connectivity.** When edges are inserted and deleted online, recomputing bridges each time is wasteful. Holm, de Lichtenberg, and Thorup (2001) maintain full connectivity — and 2-edge-connectivity — under arbitrary updates in $O(\log^2 n)$ amortized time per operation using a hierarchy of spanning forests.[^hdt] This is the data structure behind interactive network-reliability tools and incremental mesh processing, where the graph changes faster than a from-scratch DFS could keep up.

## 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 $\iff low[v] > disc[u]$.
  **Articulation criterion:** a non-root $u$ is a cut vertex $\iff$ some child has
  $low[v] \ge disc[u]$; the root is a cut vertex $\iff$ 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**.

[^skiena-conn]: **Skiena**, §5 — Graph Traversal: edge- and vertex-connectivity, and articulation vertices as the weak points found by DFS low-links.
[^clrs-dfs]: **CLRS**, Ch. 22 — Elementary Graph Algorithms (DFS): an undirected DFS yields only tree and back edges; the parenthesis/white-path structure that grounds the low-link argument.
[^erickson-dfs]: **Erickson**, Ch. 6 — Depth-First Search: Tarjan's low-link computation for bridges, articulation points, and biconnected components in linear time.
[^hopcroft-tarjan]: **Hopcroft, J. & Tarjan, R. E.** (1973), "Algorithm 447: efficient algorithms for graph manipulation," _Communications of the ACM_ 16(6), 372–378 — biconnected components and the block-cut structure via DFS.
[^hdt]: **Holm, J., de Lichtenberg, K. & Thorup, M.** (2001), "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity," _Journal of the ACM_ 48(4), 723–760.