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

---

The scenario matrix

Before working examples, let us list every case class the topic can produce. Every worked example below is tagged with the cell(s) it covers.

Cell	Structural situation	What we expect to find
A	A pure cycle (every edge on one loop)	0 bridges, 0 articulation points
B	A pure path / chain (a line of nodes)	every edge a bridge, every internal node an AP
C	Root with $\ge 2$ children (star / hub)	root is AP, its edges may or may not be bridges
D	A subtree hanging off a cycle by ONE edge	that one edge is a bridge; the attach node is an AP
E	A back edge to $u$ itself (the $\text{low}[v]=\text{disc}[u]$ tie)	NOT a bridge, but $u$ still an AP
F	Degenerate: single vertex, no edges	0 of each — nothing to remove
G	Degenerate: two vertices, one edge	that edge is a bridge; neither vertex is an AP
H	Disconnected graph (two components)	each component analysed independently
I	Multi-edge (two parallel edges) trap	the naive v == parent skip lies
J	Word problem (real network)	translate → run → interpret
K	Exam twist (mixed graph, find both sets)	full trace, both answers

We now cover all eleven cells with 9 examples. Watch the tags.

---

Example 1 — the pure cycle (cell A)

Forecast: Every node sits on one loop, so each has a "way around". Guess the counts before reading on — how many bridges? How many APs?

1. Start DFS at 0, going $0\to 1\to 2\to 3$ as tree edges. Why this step? DFS explores as deep as it can first; that produces the chain $0$–$1$–$2$–$3$ as the tree edges (black in the figure), leaving one leftover edge.
2. Assign disc as we descend: $\text{disc}[0]=0,\text{disc}[1]=1,\text{disc}[2]=2,\text{disc}[3]=3$. Initialise each $\text{low}=\text{disc}$ (source 1). Why this step? $\text{low}[u]$ must start at "I can at least reach myself" $=\text{disc}[u]$ — the recurrence only ever lowers it from there.
3. At node 3, the edge $3-0$ is a back edge (0 is a visited ancestor, and 0 is not 3's DFS parent). Apply source 3 of the recurrence: $\text{low}[3]=\min (3,\text{disc}[0]=0)=0$. Why this step? A back edge lets the whole loop "escape" all the way up to the discovery time of 0. This is the red arrow in the figure — the shortcut rope.
4. Unwind low values up the chain (source 2): $\text{low}[2]=\min (2,\text{low}[3]=0)=0$; $\text{low}[1]=\min (1,0)=0$; $\text{low}[0]=\min (0,0)=0$. Why this step? Each parent inherits the lowest reach of its child's subtree.
5. Bridge test on each tree edge $(u,v)$: need $\text{low}[v]>\text{disc}[u]$.
   • $(0,1)$: $\text{low}[1]=0>\text{disc}[0]=0$? No ($0>0$ false).
   • $(1,2)$: $0>1$? No. $(2,3)$: $0>2$? No. Zero bridges.
6. AP test: root 0 has only one tree child (node 1) → not an AP by the root rule. For non-root $u$ we need some child $v$ with $\text{low}[v]\ge \text{disc}[u]$; but every $\text{low}[v]=0$ and every $\text{disc}[u]\ge 0$ with equality only at node 0 (a child of nobody). Check node 1: child 2 has $\text{low}[2]=0\ge \text{disc}[1]=1$? $0\ge 1$ false. Zero APs.

Verify: Physically remove any one edge, say $2-3$: the loop becomes the path $3-0-1-2$, still one connected piece. Remove any one vertex, say 1: $0-3-2$ survives connected. Matches 0 and 0. ✓

---

Example 2 — the pure chain (cell B, and cell G inside it)

Forecast: No loops at all. Cut any edge and the line snaps into two. Remove any middle node and the line snaps. Guess: how many bridges, how many APs?

1. DFS from 0 produces exactly the chain as tree edges; there are no back edges because there is no loop. Why this step? Without a cycle there is no ancestor to jump back to, so every $\text{low}[u]$ stays equal to its own $\text{disc}[u]$.
2. disc = low = $(0,1,2,3)$ for nodes $(0,1,2,3)$. Why this step? Source 3 (back edge) never fires; source 2 only copies a child's $\text{low}$, and here each leaf's low equals its own disc, so nothing decreases.
3. Bridge test: $(2,3)$: $\text{low}[3]=3>\text{disc}[2]=2$ ✓ bridge. $(1,2)$: $2>1$ ✓ bridge. $(0,1)$: $1>0$ ✓ bridge. All three edges are bridges. Why this step? Each subtree can reach only itself, strictly below its parent — the textbook bridge condition.
4. AP test: root 0 has one child → not AP. Node 1 (non-root): child 2 has $\text{low}[2]=2\ge \text{disc}[1]=1$ ✓ → 1 is AP. Node 2 (non-root): child 3 has $\text{low}[3]=3\ge \text{disc}[2]=2$ ✓ → 2 is AP. Node 3 is a leaf (no children) → not AP. APs = {1, 2}.

Verify: Remove node 1 → $\{0\}$ and $\{2,3\}$: two components ✓. Remove node 2 → $\{0,1\}$ and $\{3\}$ ✓. Remove an endpoint 0 → $\{1,2,3\}$ still one piece → correctly NOT an AP. Bridges = 3, APs = {1,2}. ✓

Cell G note: the smallest chain, a single edge $0-1$, is contained here: that edge is a bridge, and neither endpoint is an AP (removing an endpoint leaves one node, still "connected" as a single component). Endpoints are never cut vertices.

---

Example 3 — the hub / star root (cell C)

Forecast: 0 is the only thing tying the three arms together. Guess before reading.

1. DFS from 0 visits 1 (dead end, back up), then 2 (dead end), then 3 → three separate tree children of the root. Why this step? There are no edges between 1, 2, 3, so DFS cannot go deeper from any of them; it returns to 0 and picks the next unvisited neighbour. That is what makes them sibling subtrees of the root.
2. disc = low = $(0,1,2,3)$; no back edges exist.
3. Root AP rule: children count of root $=3\ge 2$ → 0 is an articulation point. Why this step? The root has no ancestor to fall back on; if it holds $\ge 2$ independent subtrees, deleting it disconnects them from each other.
4. Bridge test: each edge $(0,k)$: $\text{low}[k]=k>\text{disc}[0]=0$ ✓ → all 3 edges are bridges.

Verify: Remove 0 → $\{1\},\{2\},\{3\}$: three components ✓ (AP confirmed). Remove edge $0-2$ → 2 isolated ✓ (bridge confirmed). Bridges = 3, APs = {0}. ✓

---

Example 4 — subtree hanging off a cycle (cells D + E, the equality tie)

Forecast: One edge is a lonely link, one node is a chokepoint, and there's a sneaky "back edge to $u$ itself" tie. Predict which edge, which node.

1. DFS $0\to 1\to 2\to 3$ as tree edges; at 3 the edge $3-1$ is a back edge to ancestor 1. Why this step? 1 is already visited and is not 3's DFS parent (2 is), so $3-1$ closes the triangle as a back edge.
2. disc = $(0,1,2,3)$. Apply source 3 at 3: $\text{low}[3]=\min (3,\text{disc}[1]=1)=1$. Why this step? The triangle's escape hatch reaches up to disc-time 1 (node 1) — but no higher, because the back edge lands on 1, not on 0.
3. Unwind (source 2): $\text{low}[2]=\min (2,1)=1$; $\text{low}[1]=\min (1,1)=1$; $\text{low}[0]=\min (0,1)=0$.
4. Bridge test:
   • $(2,3)$: $\text{low}[3]=1>\text{disc}[2]=2$? No.
   • $(1,2)$: $\text{low}[2]=1>\text{disc}[1]=1$? No — it's a tie, $1>1$ is false. (cell E)
   • $(0,1)$: $\text{low}[1]=1>\text{disc}[0]=0$? Yes → BRIDGE. (cell D)
5. AP test (uses $\ge$, so ties DO cut):
   • Node 1 (non-root), child 2: $\text{low}[2]=1\ge \text{disc}[1]=1$? Yes → 1 is an AP. This is the exact place where the tie matters: the edge $1-2$ is not a bridge (source of a back edge into 1), yet the vertex 1 is still critical.
   • Node 2, child 3: $\text{low}[3]=1\ge \text{disc}[2]=2$? No. Node 0 is root with one child → not AP.

Verify: Remove edge $0-1$ → $\{0\}$ alone, triangle separate → bridge ✓. Remove edge $1-2$ → $0-1-3-2$ still connected → NOT a bridge ✓. Remove vertex 1 → $\{0\}$ and $\{2,3\}$: two components → 1 is AP ✓. Bridges = {(0,1)}, APs = {1}. ✓

---

Example 5 — a single vertex (cell F, degenerate)

Forecast: There is literally nothing to remove. Guess the counts.

1. DFS from 0: the loop for v in adj[0] never runs (empty adjacency). children = 0. Why this step? No neighbours means no tree edges and no back edges — the recurrence has only source 1: $\text{low}[0]=\text{disc}[0]=0$.
2. Root rule: children $=0$, which is not $\ge 2$ → 0 is not an AP.
3. Bridge list stays empty — there is no edge to test.

Verify: Removing the only vertex leaves the empty graph. The component count goes from 1 to 0, which is not an increase — so by definition (removal must increase components) it is not an articulation point. Bridges = 0, APs = 0. ✓

---

Example 6 — a disconnected graph (cell H)

Forecast: The algorithm's outer for s in range(n) restarts DFS on each unvisited node. So it will handle P, then Q, as two independent runs. Predict each piece's answer, then combine.

1. First DFS from 0 covers P: as in cell G, edge $0-1$ is a bridge, neither endpoint an AP. Why this step? The outer loop guarantees every component gets its own DFS root with $parent=-1$, so Connected Components are analysed independently — no interaction leaks across pieces.
2. After P, disc of 2,3,4 is still $-1$. The outer loop finds 2 unvisited → new DFS root 2, timer continues from where it left off (say $\text{disc}[2]=2$). Why this step? Timestamps keep counting globally, but that is harmless: comparisons only happen within one subtree, so cross-component times never mix.
3. Q is a triangle → by cell A, 0 bridges, 0 APs inside Q.
4. Combine: whole-graph bridges $=\{(0,1)\}$; whole-graph APs $=\varnothing$.

Verify: Component count starts at 2. Removing edge $0-1$ → P splits → 3 components (increase) → bridge ✓. Removing edge $3-4$ → Q still a path $2-3\&4-2$, still connected → 2 components (no increase) → not a bridge ✓. Bridges = 1, APs = 0. ✓

---

Example 7 — the parallel-edge trap (cell I)

Forecast: There are two independent roads between the same pair of towns. Cutting one leaves the other. So — bridge or not? And will the naive code get it right?

1. Truth first: with two parallel edges, removing one still leaves the other → neither edge is a bridge, and neither vertex is an AP. Why this step? Bridge means removal disconnects; a redundant twin prevents that.
2. What the naive v == parent code does: DFS $0\to 1$ down edge #1 (tree edge). At 1, we look at neighbour 0 via edge #2. The code checks v == parent → 0 == 0 → skips it, thinking it is the edge we came down on. But it isn't — it's the second edge! Why this step? Skipping by vertex identity cannot tell the two edges apart, so the genuine back-route (edge #2) is invisible. Then $\text{low}[1]$ stays $=\text{disc}[1]=1$, and the bridge test $\text{low}[1]=1>\text{disc}[0]=0$ fires → falsely reports a bridge.
3. Fix: skip the parent edge by edge-id, once. Pass the id of the edge you descended on; only skip that id. The second parallel edge is then treated as a proper back edge (source 3), lowering $\text{low}[1]$ to $\text{disc}[0]=0$, and $0>0$ is false → correctly no bridge.

Verify: With the edge-id fix, $\text{low}[1]=\min (1,\text{disc}[0]=0)=0$; bridge test $0>0$ is false ✓. Removing one of the two edges physically leaves 0 and 1 still joined → not a bridge ✓.

---

Example 8 — real-world word problem (cell J)

Forecast: The loop A–B–C is robust; the tail C–D–E is a dangling chain. Which pipes and which stations are critical? Predict, then trace.

1. Translate to a graph and DFS from 0(A): $0\to 1\to 2$ (tree edges), the edge $2-0$ is a back edge closing the loop, then $2\to 3\to 4$ (tree edges) down the tail. Why this step? Modelling "burst pipe → split" is exactly the bridge question; "shut station → split" is exactly the articulation question. The picture is the graph.
2. Assign disc as we descend: $\text{disc}=(0,1,2,3,4)$ for $(0,1,2,3,4)$; initialise $\text{low}=\text{disc}$ (source 1). Why this step? Standard start — every vertex reaches at least itself.
3. Back edge at 2 (source 3): $2-0$ lands on ancestor 0, so $\text{low}[2]=\min (2,\text{disc}[0]=0)=0$. In the tail there is no back edge, so $\text{low}[4]=4$ and $\text{low}[3]=4$ stay high. Why this step? The loop collapses its low to 0 (robust, like cell A); the tail keeps low = disc (fragile, like cell B). This split is the whole answer in miniature.
4. Unwind (source 2): $\text{low}[3]=\min (3,\text{low}[4]=4)=3$; $\text{low}[2]=\min (0,\text{low}[3]=3)=0$; $\text{low}[1]=\min (1,\text{low}[2]=0)=0$; $\text{low}[0]=\min (0,0)=0$. Why this step? Each parent absorbs the best reach of its child's subtree; the tail's high lows never leak into the loop.
5. Bridge test on every tree edge:
   • loop edges $(0,1)$: $\text{low}[1]=0>\text{disc}[0]=0$? no. $(1,2)$: $\text{low}[2]=0>\text{disc}[1]=1$? no. — loop is bridge-free.
   • $(2,3)$: $\text{low}[3]=3>\text{disc}[2]=2$? yes → pipe C–D is critical.
   • $(3,4)$: $\text{low}[4]=4>\text{disc}[3]=3$? yes → pipe D–E is critical.
6. AP test:
   • Node 2(C), child 3: $\text{low}[3]=3\ge \text{disc}[2]=2$ ✓ → station C is critical.
   • Node 3(D), child 4: $\text{low}[4]=4\ge \text{disc}[3]=3$ ✓ → station D is critical.
   • Node 1(B), child 2: $\text{low}[2]=0\ge \text{disc}[1]=1$? no → B not critical. Node 4(E) is a leaf → not critical. Root 0(A) has one tree child → not critical.

Verify: Burst pipe C–D → {A,B,C} vs {D,E}: split ✓. Burst A–B → A–C–B still connected via the loop → not critical ✓. Shut C → {A,B} vs {D,E}: split ✓. Shut D → {A,B,C} vs {E}: split ✓. Critical pipes = {C–D, D–E}, critical stations = {C, D}. ✓

---

Example 9 — exam twist: find both sets on a mixed graph (cell K)

Forecast: Two robust loops joined by one thin edge $1-3$. Predict: the thin edge is the only bridge; the two nodes at its ends are the cut vertices. Write your guess, then check.

1. DFS from 0: tree edges $0\to 1\to 2$, then back edge $2-0$ closes loop A; from 1 the tree edge $1\to 3$, then $3\to 4\to 5$, and back edge $5-3$ closes loop B. Why this step? Two cycles means two escape hatches — each loop's nodes get a low that collapses to that loop's top; the joining edge $1-3$ has no loop covering it, so it stands alone.
2. Assign disc as we descend: $\text{disc}=(0,1,2,3,4,5)$ for $(0,1,2,3,4,5)$; initialise $\text{low}=\text{disc}$ (source 1).
3. Back edges (source 3): loop A gives $\text{low}[2]=\min (2,\text{disc}[0]=0)=0$. Loop B gives $\text{low}[5]=\min (5,\text{disc}[3]=3)=3$. Why this step? Loop B's back edge lands on 3, so its subtree reaches only down to disc-time 3 — never up to 1. That is the fingerprint of a bridge sitting above it.
4. Unwind (source 2): $\text{low}[4]=\min (4,\text{low}[5]=3)=3$; $\text{low}[3]=\min (3,\text{low}[4]=3)=3$; at node 1, $\text{low}[1]=\min (\text{disc}[1]=1,\text{low}[2]=0,\text{low}[3]=3)=0$; $\text{low}[0]=\min (0,\text{low}[1]=0)=0$.
5. Bridge test on every tree edge:
   • Loop A: $(0,1)$ $\text{low}[1]=0>\text{disc}[0]=0$? no; $(1,2)$ $\text{low}[2]=0>\text{disc}[1]=1$? no.
   • $(1,3)$: $\text{low}[3]=3>\text{disc}[1]=1$? yes → BRIDGE.
   • Loop B: $(3,4)$ $\text{low}[4]=3>\text{disc}[3]=3$? no; $(4,5)$ $\text{low}[5]=3>\text{disc}[4]=4$? no.
6. AP test:
   • Node 1 (non-root), child 3: $\text{low}[3]=3\ge \text{disc}[1]=1$ ✓ → 1 is an AP (its other child 2 gives $\text{low}[2]=0\ge 1$? no — but one qualifying child is enough).
   • Node 3, child 4: $\text{low}[4]=3\ge \text{disc}[3]=3$ ✓ → 3 is an AP.
   • Root 0: one tree child (node 1) → not AP. Nodes 2,4,5: no failing child → not APs.

Verify: Remove edge $1-3$ → loop A {0,1,2} vs loop B {3,4,5}: split ✓ (only bridge). Remove vertex 1 → loop B side {3,4,5} cut from {0,2} → 1 is AP ✓. Remove vertex 3 → {4,5} cut from {0,1,2} → 3 is AP ✓. Bridges = {(1,3)}, APs = {1,3}. ✓

---

The matrix, filled in

Recall Which example covered which cell?

A→Ex1, B→Ex2, C→Ex3, D+E→Ex4, F→Ex5, G→Ex2/Ex6, H→Ex6, I→Ex7, J→Ex8, K→Ex9. Every cell is worked.

Recall One-line reflex

Bridge when $\text{low}[v]>\text{disc}[u]$ (strict, edge); AP-nonroot when $\text{low}[v]\ge \text{disc}[u]$ (equality, vertex); AP-root when it has $\ge 2$ DFS children.

Related structures you can now read the same way: Biconnected Components (maximal chunks with no internal AP), Bridge Trees / 2-edge-connected components (contract every non-bridge into a node), and the directed cousin Strongly Connected Components - Tarjan which reuses the very same low-link idea.