Articulation points and bridges — Tarjan's low-link values: Visual walkthrough

Step 1 — Draw the graph and name what a "cut" even means

WHAT. We start with a plain undirected graph: dots (called vertices) joined by lines (called edges). A dot is a place; a line is a two-way road between two places.

WHY. Before we compute anything, we must see the thing we are hunting. A bridge is one line that, if erased, splits the picture into two pieces that no longer touch. An articulation point is one dot that, if erased along with all lines touching it, does the same. These are the single points of failure.

PICTURE. Below, the graph has vertices $0, 1, 2, 3$ with edges $0 - 1$ , $1 - 2$ , $2 - 3$ , $3 - 1$ . The red line $0 - 1$ is the one we will prove is a bridge. Notice the triangle $1 - 2 - 3$ on the right: those three are held together by three roads, so none of them is fragile — but the single road reaching that triangle from vertex $0$ is.

Figure — Articulation points and bridges — Tarjan's low-link values

Step 2 — Run DFS and watch the tree grow (this is where `disc` is born)

WHAT. A Depth-First Search walks as deep as it can before backing up. Each time it steps to a brand-new vertex, it uses a tree edge (a solid arrow, "the way down"). The order of first visits gives us $disc$ .

WHY. DFS turns a tangled graph into a clean tree hanging from the start vertex. On that tree, every non-tree edge is a back edge — a dashed line jumping from a vertex up to one of its own ancestors. (In an undirected graph, DFS never makes cross or forward edges — a fact we lean on completely.) So the whole structure is just: a spine of tree edges, plus a few dashed shortcuts.

PICTURE. Start at $0$ . Go $0 \to 1 \to 2 \to 3$ (solid, timestamps $0, 1, 2, 3$ ). From $3$ there is an edge to $1$ , but $1$ is already visited and is an ancestor — that is the dashed back edge.

Step 3 — Seed `low`: every vertex can at least reach itself

WHAT. Before any climbing, set $low [u] = disc [u]$ for every vertex the instant we discover it.

WHY. $u$ can trivially "reach" its own arrival time — you are standing on your own platform. This is the honest starting guess; every rule after this can only lower it (find something older and higher to swing to), never raise it. That is why $low$ is a running minimum.

PICTURE. Each vertex gets two stacked numbers: $disc$ on top (fixed forever) and $low$ below (will still change). Right now they are equal everywhere.

Step 4 — Fire the back edge: `low` drops using `disc[w]`, not `low[w]`

WHAT. We are at the deepest vertex $3$ . Its edge to $1$ leads to an already-visited ancestor — a back edge. We update: $low [3] = min (low [3], disc [1]) = min (3, 1) = 1.$

WHY. A back edge is a one-hop shortcut up to ancestor $1$ . Landing on $1$ means we can reach $1$ 's timestamp, which is $disc [1] = 1$ — an older, higher platform than $3$ 's own $3$ . We take the smaller. Crucially we use $disc [1]$ (how high the jump landed) and not $low [1]$ . Using $low [1]$ would pretend the back edge lets us continue beyond $1$ through $1$ 's other shortcuts — a path that does not actually exist. So back edges record the landing spot, tree children pass along the whole reachable minimum (that comes next).

PICTURE. The dashed arrow $3 ⇢ 1$ lights up; the $low$ number under $3$ ticks from $3$ down to $1$ . The label on the arrow reads disc[1]=1, not low[1].

Step 5 — Back up the spine: children hand their `low` to the parent

WHAT. DFS finishes with $3$ and returns to $2$ . Now $2$ absorbs its child's value: $low [2] = min (low [2], low [3]) = min (2, 1) = 1.$ Return to $1$ : $low [1] = min (1, low [2]) = min (1, 1) = 1$ .

WHY. This is the tree-child rule, and it is different from the back-edge rule. Anything the child's entire subtree can escape to is also escapable from the parent — you can always walk down into the child and use whatever shortcut it found. So the parent inherits the child's full $low$ . This is how a shortcut discovered deep inside a subtree (the $3 ⇢ 1$ jump) propagates all the way up the spine to $1$ .

PICTURE. Watch the value $1$ climb: it is born at $3$ , flows up to $2$ , then to $1$ . The chain of $low$ numbers now reads $1, 1, 1$ on the triangle — that entire subtree can reach platform $1$ .

Step 6 — The bridge test emerges: compare `low[1]` with `disc[0]`

WHAT. We finish the triangle and return to the root $0$ . Look at its child $1$ : $low [1] = 1 > disc [0] = 0 \Rightarrow (0, 1) is a BRIDGE.$ Meanwhile inside the triangle: $low [3] = 1 \leq disc [2] = 2$ and $low [2] = 1 \leq disc [1] = 1$ , so edges $(2, 3)$ and $(1, 2)$ are not bridges.

WHY. $low [1]$ is the highest place $1$ 's whole subtree can escape to. If that height is still strictly below $0$ (bigger timestamp than $disc [0]$ ), then the subtree can reach neither $0$ nor anything above $0$ — except by walking back through the single edge $(0, 1)$ . Erase that edge and the subtree floats away. That is precisely $low [v] > disc [u]$ . The inequality is strict: if $low [v]$ equalled $disc [u]$ , a back edge would reach $u$ itself, giving an alternate route — no bridge.

PICTURE. The edge $0 - 1$ glows red. Above it float the two numbers being compared: $low [1] = 1$ versus $disc [0] = 0$ , with a big > between them.

Step 7 — The articulation test, and why `≥` not `>`

WHAT. Same numbers, one weaker inequality. A non-root vertex $u$ with tree child $v$ is an articulation point iff $low [v] \geq disc [u]$ . In our graph, vertex $1$ has child $2$ with $low [2] = 1 \geq disc [1] = 1$ — so $1$ is an articulation point (equality case!).

WHY. Now we delete the vertex $u$ , not just one edge. Suppose $v$ 's subtree has a back edge landing exactly on $u$ (so $low [v] = disc [u]$ ). For a bridge that back edge saved us — $u$ was still reachable. But once we remove $u$ entirely, that back edge dies with it, and the subtree is stranded. So equality still cuts. Hence $\geq$ for vertices, $>$ for edges — the single symbol difference encodes "we deleted the landing spot itself."

PICTURE. Left panel: cut the edge into $1$ — the triangle still hangs on via the $3 ⇢ 1$ shortcut (not a bridge from $1$ 's side). Right panel: cut the vertex $1$ — the shortcut vanishes with it and the triangle drops off. Same numbers, different verdict.

Step 8 — Degenerate case: the root has no ancestor (the ≥2-children rule)

WHAT. The root of the DFS tree has no parent, so the test $low [v] \geq disc [u]$ is meaningless for it (there is nothing above to be cut off from). The root gets its own rule: it is an articulation point iff it has $\geq 2$ tree children.

WHY. The root sits at the very top; no vertex is older. If DFS launched two or more separate tree children from the root, those subtrees had no way to reach each other except through the root (otherwise DFS would have merged them into one subtree). Remove the root and they split. One child ⇒ nothing to disconnect. In the star graph $1 - 0, 2 - 0, 3 - 0$ , DFS from $0$ makes three separate children $\Rightarrow 0$ is an articulation point.

PICTURE. Root $0$ with three fan-out tree edges to $1, 2, 3$ , no edges among them. Delete $0$ and the picture shatters into three lone dots.

The one-picture summary

Everything compressed: the spine of $disc$ timestamps, the one dashed shortcut, the $low$ values flowing up, and the single red bridge where $low [v] > disc [u]$ . All of Tarjan lives in this one frame — one Depth-First Search pass, $O (V + E)$ by Big-O Notation.

Recall Feynman: tell the whole walkthrough to a 12-year-old

You explore a treehouse fort, climbing down ropes to new platforms. The order you first reach each platform is its $disc$ number — platform $0$ first, then $1$ , then $2$ , then $3$ . Along the way you sometimes spot a secret shortcut rope going back up to an older platform; the oldest platform you can swing back to (using one shortcut) is your $low$ number. When you climb back up the ropes, you tell your parent platform the lowest number you found, so good shortcuts travel all the way up the fort. At the end you check each rope: if the whole section below a rope can only swing back to itself, never higher than where the rope hangs ( $low [v] > disc [u]$ ), that rope is the only thing holding the section up — a bridge. And if a whole section can't get past a certain platform without stepping on it ( $low [v] \geq disc [u]$ ), that platform is a must-not-break support — an articulation point. The very top platform is special: it's a support only if it launched two or more separate sections.

Recall Two-line self-test

Why disc[w] (not low[w]) on a back edge? ::: A back edge only tells you how high you landed; using low[w] would credit paths past the landing spot that don't exist, over-lowering low and hiding real bridges. Why is the bridge test strict > but the articulation test ≥? ::: A bridge deletes only the edge, so a back edge reaching u itself still saves connectivity; an articulation deletes the whole vertex u, killing that back edge too — so equality still disconnects.