Lesson · Graph Algorithms · Searching a graph

Bridges and Cut Vertices

An edge whose removal disconnects the graph is a bridge; a vertex whose removal does the same is a cut vertex. Both can be found by deleting each candidate and recounting the components, which costs a walk per candidate. One extra number per vertex — the earliest discovery time reachable from its subtree — finds all of them in a single walk, and the lab runs the slow method beside it on the graph you typed.

Open the interactive lesson Practice

low[v] = min over the subtree at v of d, using at most one non-tree edge tree edge (u, v) is a BRIDGE when low[v] > d[u] non-root u is a CUT VERTEX when some child v has low[v] >= d[u] the root is a cut vertex when the walk gave it two or more children exclusion is by ARC, not by endpoint: a second edge to the parent is a back edge

One extra number per vertex, and the three rules it feeds

Core ideas

What this lesson establishes

The hard idea is low, and specifically what it is allowed to use. The two rules that read it, and the root's exception, follow from the definition.

low[v] is the highest the subtree at v can climb

Write low[v] for the smallest discovery time reachable from v by going down any number of tree edges and then along at most one non-tree edge. It is computed as v closes, from d[v], from the low of each child, and from the d of each vertex a non-tree edge from v reaches. On the lab's opening graph the discovery times are 1, 2, 3, 4, 5, 6 in order and the low values come out 1, 1, 1, 4, 4, 4 — two blocks of three, and the boundary between them is the answer.

A bridge is a subtree with no way back above its own parent

For a tree edge (u, v), the subtree at v is cut off by removing that edge exactly when nothing in the subtree reaches u or higher by another route — that is, low[v] > d[u]. Every non-tree edge is a back edge in an undirected walk, so “another route” means exactly what low measures. On the opening graph that fires once, at the edge between 3 and 4.

The root needs its own rule, and it is about children

For a non-root u, a child v with low[v] >= d[u] means the subtree cannot get past u, so deleting u strands it. The root has no parent to be stranded from, so that test is vacuous; instead the root is a cut vertex exactly when the walk gave it two or more children, because a second child means a part of the graph that only the root connected. The lab ships a preset for this: on four vertices with arcs 1-2, 1-3, 2-3, 1-4 the root 1 is the only cut vertex.

The material

One more number, and the two rules that read it

The definitions, what low means precisely, the two tests, the root exception, and the graph the matrix check cannot be given.

Definition · Bridge and cut vertex

An edge of a connected undirected graph is a bridge if deleting it leaves a graph with more components. A vertex is a cut vertex if deleting it, and every edge at it, does the same. Neither definition mentions an algorithm, and the slow method is a direct transcription of them: delete, recount, restore.

That slow method costs one walk per candidate, so Θ(E(V + E)) for the edges. It is also completely reliable, which is why the lab runs it as an independent answer beside the fast one rather than as a fallback. On the opening graph both report the single bridge between 3 and 4 and the two cut vertices 3 and 4, and the panel prints the comparison rather than the agreement it expects.

Definition · The low-link value

For a vertex v of a depth-first forest on an undirected graph, low[v] is the minimum of d[v], of low[c] over the children c of v, and of d[w] over every vertex w joined to v by a non-tree edge. Equivalently it is the smallest discovery time reachable from v using tree edges downwards and then at most one non-tree edge.

The recursive form is what makes it computable in the walk: low[v] is finished exactly when v closes, because by then every child has closed and every edge at v has been examined. So the cost is the walk's cost and nothing more. On the opening graph the panel counts 6 vertex visits and 18 edge reads, against Θ(V + E) — 18 rather than 7 because each edge is considered from both of its ends, the adjacency index holds it at each end both as leaving and as entering, and the one arc the walk arrived on is skipped at every vertex but the root.

Theorem · The bridge test

Let (u, v) be a tree edge with v the child. Then (u, v) is a bridge if and only if low[v] > d[u].

Suppose low[v] > d[u]. Every vertex in the subtree at v has all its edges going either inside that subtree or upwards to a vertex discovered no earlier than v — if any went to something discovered before u or to u itself, low[v] would be at most d[u]. So the only edge leaving the subtree is (u, v), and deleting it separates the subtree from the rest.

Conversely, suppose low[v] ≤ d[u]. Then some vertex x in the subtree at v has a non-tree edge to a vertex discovered at or before u, which in an undirected walk means an ancestor of v at or above u. The tree path from v down to x, that edge, and the tree path back down to v form a cycle through (u, v), and no edge on a cycle is a bridge.

□

Example · Two triangles joined by one edge

The lab opens on 1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4. The walk discovers the vertices in order, so d is 1, 2, 3, 4, 5, 6, and the low values are 1, 1, 1, 4, 4, 4. The tree edge from 3 to 4 has low[4] = 4 > d[3] = 3, so it is a bridge; every other tree edge fails the test because its child sits on a triangle and can climb back. Cut vertices: 3, because its child 4 has low[4] >= d[3], and 4, because its child 5 has low[5] = 4 >= d[4] = 4. Delete-and-recount returns the same three answers.

The two tests are nearly the same and differ by one comparison

The bridge test is low[v] > d[u] and the cut-vertex test is low[v] >= d[u]. Equality is the case where the subtree can climb back to u itself but no higher: then the edge (u, v) lies on a cycle and is not a bridge, while u is still the only way in and out, so u is a cut vertex. The lab's opening graph has both endpoints of its bridge as cut vertices; its path preset has four bridges and three cut vertices, because the two ends of a path are on a bridge without being cut vertices.

And in the other direction, a cut vertex need not be on a bridge at all. Two triangles sharing a single vertex have that vertex as a cut vertex and no bridge anywhere, because every edge is on a triangle. Neither concept implies the other, and a reader who has only seen the opening graph will believe they come in pairs.

Exclusion is by arc, and that is not a technicality

The walk must not follow the edge it arrived on, and the way to enforce that is to remember the EDGE and not the parent vertex. With two edges between the same pair, remembering the parent vertex would ignore both, and the graph would be reported as having a bridge that it does not have. The lab ships this as a preset: on 1-2, 1-2, 2-3 the only bridge is the one between 2 and 3, whereas with a single edge between 1 and 2 the same three vertices give two bridges.

That preset is also where the independent check stops. The delete-and-recount oracle works on an adjacency matrix, which holds one entry per pair of vertices and therefore cannot represent two edges between the same pair at all. The panel says so, in those words, rather than comparing against a different graph and reporting agreement. A checker that quietly answers a question you did not ask is worse than one that declines.

Put the two figures side by side one last time. On the opening graph: 6 visits and 18 reads for the one-pass method, against a delete-and-recount that runs a fresh traversal for each of the 7 edges. Those are measurements on that graph. The bound is that the one-pass method is Θ(V + E) on every graph, and the reason is that low is completed at the moment a vertex closes, so no vertex and no edge is revisited.

Interactive

Bridges and cut vertices by low-link

One pass computes what deleting every edge in turn also computes, and the page runs both

Type the graph, then try to break the rules

The low-links come from one depth-first pass. The bridges and cut vertices are then found again the slow way — delete each edge, recount the components — and the two answers are compared in front of you. Type two edges between the same pair and the slow method declines rather than answering about another graph.

Worked example

Edges, as one−other

Bridges—

Cut vertices—

Pieces the graph is already in—

Agrees with delete-and-recount—

Edges examined by the brute force—

Parallel pairs a matrix cannot hold—

An edge is 1−2. low(v) is the earliest discovery time reachable from v's subtree using tree edges and at most one back edge, and the tree edge into v is a bridge exactly when low(v) > d(u) — nothing in v's subtree can get above u without it. Write a second edge between the same pair and watch a bridge stop being one.

Method

Finding the weak points of a graph

Compute d on the way down and low on the way back up; then read the two rules.

Write d as you descend and low as you return

d[v] is fixed the moment v is reached. low[v] is not fixed until v closes, because it takes the minimum over children that have not been explored yet. Recording low too early is the single commonest way to get this wrong by hand.

Fold in three things, and only three

d[v] itself, low[c] for each child c, and d[w] for each non-tree edge to w. Note the asymmetry: a child contributes its low, but a back edge contributes the other end's d. Using low[w] for a back edge is wrong and produces values that are too small, which hides bridges.

Apply the two tests, and remember the root is different

Strictly greater for a bridge, greater or equal for a cut vertex, and for the root of each tree in the forest, count its children instead. The lab's root preset exists because this exception is the one readers drop.

Check against deletion on something small

Delete an edge, recount the components, restore it. It is the definition, it is cheap on a graph you can draw, and it is what the panel runs beside the fast method. Where the two disagree, the fast one is the one to distrust.

Low values, and the two rules

Score 0 / 0

Choose the answer you can justify.

Two triangles, one bridge, and the low values that find it

The graph is 1-2, 2-3, 3-1, 3-4, 4-5, 5-6, 6-4. The walk starts at 1 and takes the edges at each vertex in the order they were typed.

vertex d low why low is that 1 1 1 its own d; nothing climbs above it 2 2 1 back edge from the subtree reaches d = 1 3 3 1 child 2's low is 1 (walk: 1 - 2 - 3) 4 4 4 its own d; the subtree at 4 never leaves 4, 5, 6 5 5 4 back edge 6 - 4 reaches d = 4 6 6 4 its own back edge to 4 bridge test on each tree edge, child first (1, 2) low[2] = 1 > d[1] = 1 ? no (2, 3) low[3] = 1 > d[2] = 2 ? no (3, 4) low[4] = 4 > d[3] = 3 ? YES -> bridge (4, 5) low[5] = 4 > d[4] = 4 ? no (5, 6) low[6] = 4 > d[5] = 5 ? no cut-vertex test, same numbers with >= 3 has child 4 with low[4] = 4 >= d[3] = 3 -> cut vertex 4 has child 5 with low[5] = 4 >= d[4] = 4 -> cut vertex 1 is the root and has one child -> not a cut vertex delete and recount: 1 bridge, cut vertices 3 and 4 agrees

Look at the pair (4, 5). Its low value equals d[4] exactly, so it fails the bridge test by one and passes the cut-vertex test by nothing. That is the whole difference between the two rules, and it is why the same walk answers both questions without a second pass.

Look also at vertex 1. The walk gave it one child, so the root rule does not fire; but if the walk had started at 3 instead, the root would have had two children and would have been reported as a cut vertex — which it is. The answer does not depend on the root, but which rule produces it does.

For a faded rehearsal, add the edge 1-5 and predict the new bridges and cut vertices before running it. The supplied first move is this: the new edge gives the subtree at 4 a way back to d = 1, so low[4] falls from 4 to 1. Say what that does to the bridge test at (3, 4), and then say which cut vertices survive.

Common mistakes

Excluding the parent by vertex rather than by edgeWith two edges between the same pair, skipping every edge to the parent vertex skips both, and the second one — which is a genuine back edge and puts the pair on a cycle — never contributes to low. The result is a reported bridge that is not one. The lab's parallel preset is exactly this case, and it is also the graph the matrix-based check has to decline.

Finalising low on the way downlow[v] takes a minimum over the low values of v's children, and those do not exist until the children have closed. Anyone computing it as the walk descends is computing something else — usually the minimum over back edges at v alone — and that value is too large, which manufactures bridges.

Assuming bridges and cut vertices come in pairsThey are different properties with different tests and the strictness of one comparison between them. A path has every interior vertex as a cut vertex and every edge as a bridge; two triangles sharing a vertex have a cut vertex and no bridges; the two ends of any bridge on a long path are on a bridge without being cut vertices. Run the lab's path and cycle presets before believing either implication.

Check your understanding

✓

Finish when you can compute every low value by hand and read both answers off them.

You should be able to run the walk recording d on the way down and low on the way back, apply the strict test for bridges and the non-strict one for cut vertices, remember the root's own rule, and say why the parent must be excluded by edge rather than by vertex.

Note: This is the second use of one walk and it will not be the last. “Strongly Connected Components” asks the directed version of the same question — which vertices can reach each other — and the answer needs two walks rather than one extra number, because in a digraph reaching and being reached are different relations.