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

Definition Vocabulary used on this page (self-contained)

Run a depth-first search (DFS) on an undirected graph. As you walk, you carve out a DFS tree:

A tree edge is an edge you use to step into a brand-new, never-seen vertex (that's how you "discover" it).
A back edge is an edge you find leading to a vertex you already visited that is an ancestor (a vertex above you on the current path). Undirected DFS produces only these two kinds — no cross or forward edges.
The parent of $v$ is the vertex $u$ from which the tree edge $u \to v$ entered $v$ ; it is the node "one step up" from $v$ on the DFS path. The root has parent $- 1$ (none).
$disc [u]$ = discovery time: an integer stamped when DFS first reaches $u$ . On this page timestamps start at $0$ and increase by $1$ each new visit (some textbooks start at $1$ ; we fix $0$ throughout so all our numbers are consistent — if you saw $1$ -based numbers elsewhere, just shift everything by one).
$low [u]$ = the smallest $disc$ value reachable from $u$ 's subtree using tree edges downward and at most one back edge — i.e. "the highest ancestor this subtree can climb back to."

Two small graphs recur below; each figure labels its vertices, edges, tree/back edges, and the critical structures so you can map the text's node names $0, 1, 2, \dots$ directly onto the picture.

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

Level 1 — Recognition

Recall Solution L1.1

Answer: (b). A bridge is an edge; an articulation point is a vertex. Statement (a) is the articulation-point definition, and (c) is only the root special-case test, not a definition at all.

Recall Solution L1.2

It is a back edge (an edge to an already-visited ancestor). Undirected DFS has only tree edges and back edges (no cross/forward edges). You update $low [u] = min (low [u], disc [w]) .$ You use $disc [w]$ , not $low [w]$ , because a back edge only records how high you jumped, not what that ancestor's subtree can further reach.

Recall Solution L1.3

Edge $(0, 1)$ . Vertex $0$ dangles off the triangle $1 - 2 - 3$ by that one edge; the triangle itself is a cycle so none of its edges is critical. That lone edge is the bridge.

Level 2 — Application

Recall Solution L2.1

Timestamps in visit order (starting at $0$ ): $disc = [0, 1, 2, 3]$ for vertices $[0, 1, 2, 3]$ .

Visit $3$ : the only non-parent neighbour is $1$ (already visited, ancestor) → back edge, so $low [3] = min (3, disc [1] = 1) = 1$ . ( $3$ can climb up to the node stamped $1$ .)
Back to $2$ : $low [2] = min (2, low [3] = 1) = 1$ . Why the minimum? $low [2]$ must record the highest (smallest-timestamp) ancestor reachable from $2$ 's subtree. Node $2$ alone reaches only itself (time $2$ ); but through its child $3$ the subtree already reaches time $1$ . The best of ${2, 1}$ is the smaller, $1$ — so $min$ picks exactly the highest escape available.
Back to $1$ : $low [1] = min (1, low [2] = 1) = 1$ . (Same logic: $1$ inherits its child's best reach.)
Back to $0$ : $low [0] = min (0, low [1] = 1) = 0$ . ( $0$ is the root, it reaches itself at time $0$ , which is already the highest possible.)

Final: $low = [0, 1, 1, 1]$ . Bridge test on tree edge $(0, 1)$ : $low [1] = 1 > disc [0] = 0$ → bridge (the subtree under $1$ never climbs as high as $0$ ). All other tree edges fail the strict test. One bridge: $(0, 1)$ .

Recall Solution L2.2

From root $0$ we discover $1, 2, 3$ as three separate tree children (no edges connect them).

Root rule: $0$ has $3 \geq 2$ children ⇒ $0$ is an articulation point.
Leaves $1, 2, 3$ have no children, so no test can flag them; each is a degree-1 leaf whose removal disconnects nothing else. Not articulation points. Answer: only $0$ .

Recall Solution L2.3

Correct update: $low [u] = min (5, disc [w] = 2) = 2$ . If you wrongly used $low [w] = 0$ you'd claim $u$ can climb to timestamp $0$ — but the back edge only lets you reach $w$ itself (time $2$ ). Whatever $w$ 's subtree reaches ( $0$ ) may go through a different branch that $u$ cannot access this way. Using $low [w]$ over-reports reachability and can hide a genuine bridge.

Level 3 — Analysis

Recall Solution L3.1

Bridge iff $low [v] > 4$ ; articulation (non-root) iff $low [v] \geq 4$ .

case	$low [v]$	bridge? ( $> 4$ )	$u$ AP? ( $\geq 4$ )
(i)	$5$	yes	yes
(ii)	$4$	no	yes
(iii)	$2$	no	no

Case (ii) is the crucial gap between the tests: $low [v] = disc [u]$ means $v$ 's subtree reaches $u$ itself (a back edge into $u$ ) but nothing above $u$ . The edge $(u, v)$ is therefore redundant (not a bridge), yet deleting the vertex $u$ still severs the subtree — so $u$ is an articulation point.

Recall Solution L3.2

DFS $0 \to 1 \to 2 \to 3$ , then back edge $3 \to 0$ .

$disc = [0, 1, 2, 3]$ .
$low [3] = min (3, disc [0] = 0) = 0$ ; this $0$ propagates up: $low = [0, 0, 0, 0]$ .
Every tree edge $(u, v)$ has $low [v] = 0 \leq disc [u]$ , never $>$ and never $\geq$ except degenerate root — check each: for parent $1$ ( $disc = 1$ ), $low [2] = 0 < 1$ ; etc.
Root $0$ has exactly one child ( $1$ ) ⇒ root rule not triggered.

Answer: $0$ bridges, $0$ articulation points. Every vertex has an alternate route around the cycle — no single failure disconnects anything. This is the smallest biconnected block bigger than an edge.

Recall Solution L3.3

False. Counterexample: two triangles sharing one vertex — vertices ${0, 1, 2}$ forming a triangle and ${2, 3, 4}$ forming another, sharing $2$ .

Vertex $2$ is an articulation point (remove it and the two triangles fall apart).
But no edge is a bridge: each edge sits inside a triangle, so cutting any single edge leaves its endpoints still connected the other way around.

So articulation points can exist with zero bridges. (The converse does hold in a useful sense: every bridge's endpoints, if non-leaf, are articulation points.)

Level 4 — Synthesis

Recall Solution L4.1

DFS goes $u \to v$ (first copy = tree edge). At $v$ , the second copy leads back to $u$ = the parent. The naïve rule if neighbour == parent: skip throws it away, so $v$ never records a back edge to $u$ and $low [v]$ stays $= disc [v] > disc [u]$ ⇒ falsely flagged as a bridge. But the two edges form a tiny cycle; neither is truly critical.

What "edge id" means and how to assign it. Store the graph as an edge list and number the edges $0, 1, 2, \dots$ in the order you read them. For an undirected edge you push it into both endpoints' adjacency lists carrying the same id — e.g. adj[u].append((v, id)); adj[v].append((u, id)). So the two parallel $u - v$ edges get different ids (say $7$ and $12$ ), even though they share the same endpoints.

Corrected code. Pass the id of the edge you descended as parentEdge (initially $- 1$ ). In the loop, iterate over (v, id) pairs and skip a neighbour only when id == parentEdge, not when v == parent:

def dfs(u, parentEdge):
    for (v, eid) in adj[u]:
        if eid == parentEdge:      # skip the ONE edge we came down
            continue
        ...                        # tree edge → recurse; else back edge

Now the second parallel edge (a different id) is correctly treated as a back edge, giving $low [v] = min (disc [v], disc [u]) = disc [u]$ , so $low [v] > disc [u]$ fails → correctly not a bridge.

Recall Solution L4.2

Using $disc = [0, 1, 2, 3]$ , $low = [0, 1, 1, 1]$ from L2.1:

Bridges: tree edge $(0, 1)$ : $low [1] = 1 > disc [0] = 0$ ⇒ bridge. No others. Bridges $= {(0, 1)}$ .
Articulation points:
- Root $0$ : only $1$ child ⇒ root rule fails ⇒ not an AP.
- Vertex $1$ (non-root), child $2$ : $low [2] = 1 \geq disc [1] = 1$ ⇒ AP.
- Vertex $2$ , child $3$ : $low [3] = 1 \leq disc [2] = 2$ , i.e. $1 \geq 2$ is false ⇒ not AP.
- Vertex $3$ : leaf, no children ⇒ not AP. Articulation points $= {1}$ .

Recall Solution L4.3

Two triangles sharing a single vertex (the L3.3 graph): edges ${(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)}$ — 6 edges, 5 vertices.

AP: only vertex $2$ (shared corner). ✔ exactly one.
Bridges: none — every edge lies inside a triangle. ✔ exactly zero. You cannot do it with fewer edges: to have zero bridges every edge must lie on a cycle, so you need at least two cycles (a single cycle has no AP), and the smallest cycles are triangles ( $3$ edges each), sharing one vertex to save an edge → $3 + 3 = 6$ .

Level 5 — Mastery

Recall Solution L5.1

Time. The DFS visits each vertex exactly once (guarded by disc[u] == -1), doing $O (1)$ work at entry. Across the whole run, the inner loop iterates over every adjacency-list entry; each undirected edge appears in exactly two lists, so total loop iterations $= 2 E$ , each $O (1)$ (a $min$ , a compare, and one insert into the articulation-point collection). Why the AP insert is $O (1)$ . Store the articulation points in a boolean array isAP of size $V$ (indexed by vertex number), not a hash set. Marking isAP[u] = True is a direct array write — a genuine worst-case $O (1)$ operation with no hashing and no resizing. (If you prefer a hash set, the insert is amortised $O (1)$ ; the array makes it unconditional, closing the gap.) Duplicate marks (a vertex flagged by several children) are harmless idempotent writes. Summing: $O (V)$ vertex work $+ O (2 E)$ edge work $\Rightarrow O (V + E)$ . Space. Arrays $disc, low, isAP$ are each size $V$ ; recursion depth $\leq V$ . Total extra memory $O (V)$ . (Same asymptotics as plain Depth-First Search — the low-link bookkeeping adds only constants.)

Recall Solution L5.2

All three ask "what is the highest ancestor a subtree can climb back to?" and store it as low. For undirected APs/bridges you allow tree edges + one back edge and compare low[v] against disc[u] ( $\geq$ / $>$ ). For directed SCCs the graph is directed, so you also track an on-stack flag and pop a component when $low [u] = disc [u]$ — the low-link marks the root of a strongly connected block instead of a cut. Contracting every 2-edge-connected component to a node and keeping only bridges yields the bridge tree, a tree because bridges are exactly the edges not on any cycle. One DFS, one low idea, three structures.

Recall Solution L5.3

Edges now: $0 - 1, 1 - 2, 2 - 3, 3 - 1, 0 - 2$ . DFS $0 \to 1 \to 2 \to 3$ .

$disc = [0, 1, 2, 3]$ .
$3$ : back edge $3 \to 1$ ⇒ $low [3] = min (3, 1) = 1$ .
$2$ : children give $low [3] = 1$ ; also back-neighbour $0$ (ancestor) ⇒ $low [2] = min (2, low [3] = 1, disc [0] = 0) = 0$ .
$1$ : $low [1] = min (1, low [2] = 0) = 0$ .
$0$ : $low [0] = min (0, low [1] = 0) = 0$ .
$low = [0, 0, 0, 1]$ .

Bridges: check tree edges — $(0, 1)$ : $low [1] = 0 > disc [0] = 0$ ? No. $(1, 2)$ : $low [2] = 0 > 1$ ? No. $(2, 3)$ : $low [3] = 1 > disc [2] = 2$ ? No. No bridges. APs: $1$ : child $2$ , $low [2] = 0 \geq disc [1] = 1$ ? No. $2$ : child $3$ , $low [3] = 1 \geq disc [2] = 2$ ? No. Root $0$ : one child ⇒ no. No articulation points. Adding $(0, 2)$ created a second escape route, destroying the bridge and the cut vertex from Graph A.

Recall One-line self-check

When does a tree edge $(u, v)$ pass the bridge test but $u$ fail the AP test? ::: When $u$ is the root with only that one child — then $low [v] > disc [u]$ can hold (bridge) yet the root rule needs $\geq 2$ children (no AP).