An undirected graph can have many cycles yet still depend on one edge to connect two large regions. Checking every edge by deleting it and rerunning a traversal repeats most of the same work. A single depth-first search can instead determine whether each child subtree has another route back to the rest of its component.
The needed information is a low-link value. Its meaning, rather than its formula alone, explains the strict comparison used to detect bridges. Edge identities also matter: two edges with the same endpoints are two different possible routes, and skipping both as “the parent connection” can invent a bridge that does not exist.
Define an edge failure relative to the original component count
Definition 10.1.1
(Bridge in an undirected multigraph)
Let be a finite undirected graph. We allow parallel edges and self-loops, and assign every edge a distinct ID. Deleting an edge removes only that particular edge. A bridge is an edge whose deletion increases the number of connected components.
The graph may already be disconnected. Its being disconnected after deletion is therefore insufficient; the component count must increase. A self-loop is never a bridge, since removing it changes no connection between distinct vertices.
Proof X-ray
A bridge is exactly an edge with no alternate endpoint path
For an edge with endpoints , suppose a path from to remains after deleting . Any route that used can replace that step by the alternate path, so no old connected component splits. Thus is not a bridge.
Conversely, if its endpoints are disconnected after deletion, their old component has split, so the component count increases. A self-loop uses the zero-length path from its endpoint to itself as an alternate path.
Removing one edge splits its old component into at most two parts: a simple old path from any vertex to either avoids the edge, or reaches before crossing it. That vertex therefore remains connected to or after deletion. A bridge increases the component count by exactly one.
For distinct endpoints, an alternate path can be chosen simple, and together with it forms a cycle. Conversely, the rest of any cycle containing is an alternate path. We count a self-loop as a cycle of length one and two parallel edges as a cycle of length two. Under these conventions, an edge is a bridge exactly when it lies on no cycle.
The DFS tree restricts where an escape edge can go
Run depth-first search, starting a new root at every unvisited vertex. Assign when a vertex is first discovered, using an increasing global clock. The discovery edges form a DFS forest. A vertex's subtree consists of it and its descendants in that forest.
In undirected DFS, every non-tree edge joins a vertex to an ancestor or descendant, allowing self-loops as a degenerate case. There are no edges between two unrelated completed DFS subtrees: when the earlier subtree examined such an edge, it would have discovered the other endpoint before finishing.
Consequently, another edge leaving a child subtree must lead to an ancestor. This is the structural fact that turns a minimum discovery time into an escape certificate.
Definition 10.1.2
(Low-link meaning and recurrence)
Define as the minimum discovery time reachable by starting at , following zero or more DFS-tree edges downward, and then taking at most one non-tree edge to an ancestor, including the option of no move at all.
Thus initialize . For a DFS child , after its traversal finishes, update with . For an already discovered neighbor reached through an edge other than the exact parent edge, update with .
Proof X-ray
Each update corresponds to an allowed route
The initial value corresponds to staying at . A route beginning with a downward tree edge to child continues as one of the routes summarized by , so the child's completed value supplies exactly those possibilities.
A non-tree edge from to an ancestor reaches discovery time directly. An already visited descendant may also appear when its edge is examined from the ancestor endpoint; its discovery time is larger than and cannot lower the value. It is harmless to apply the same minimum update.
Every permitted downward route either stays at the current vertex or first enters one child subtree. These cases cover the definition, so induction over DFS returns proves the recurrence. The parent tree edge is excluded: immediately returning through the very edge under examination is not an alternate route.
Low-link values are discovery times, not component sizes, numbers of back edges or shortest-path lengths. A child value is complete only after all its descendants have been processed.
Common mistake
(Testing a child before it returns)
A child's low value is final only after all its descendants have been processed. In the triangle explored from , vertex 2 starts with . Testing that initial value against would call edge a bridge, but the non-tree edge from 2 to 0 lowers to , so it is not.
The bridge test is a strict inequality
Theorem 10.1.3
(Bridge criterion for DFS tree edges)
Let be the tree edge from to its DFS child . Then is a bridge if and only if . Every non-tree edge, including a self-loop, lies on a cycle and is not a bridge.
Proof X-ray
A tree edge from u to v is a bridge exactly when low[v] > tin[u]
Let be a DFS child of , and consider the cut separating 's entire subtree from the rest of its connected component. Their tree edge crosses this cut. Any other crossing edge must be a non-tree edge from a descendant of to or an ancestor of .
Such an edge exists exactly when . It supplies a route around the parent tree edge: move within the child subtree to that edge, cross to the ancestor side, and use tree paths there. The alternate-path characterization therefore says the parent edge is not a bridge.
If , no other edge crosses the cut. Removing the parent tree edge disconnects the whole child subtree, making it a bridge. Non-tree edges themselves lie on a cycle with a tree path and cannot be bridges.
Equality is important: means there is another route back to itself. That is already sufficient to bypass the tree edge. Using instead of would falsely mark such cycle edges.
Skip the parent edge, not every edge to the parent vertex
Counterexample mode
Parallel edges expose the difference
Take two vertices 0 and 1 joined by edges with IDs 0 and 1. DFS discovers vertex 1 using edge 0. At vertex 1, skip edge 0, which is the reverse incidence of its parent tree edge. Edge 1 still leads back to vertex 0 and lowers to .
Neither edge is a bridge: deleting either leaves the other connecting the vertices. A program that skips every adjacency entry whose neighbor equals the parent vertex would skip both edges. It would leave the child's low value too high and incorrectly declare the tree edge a bridge.
Distinct edge IDs preserve the physical difference between the traversed parent edge and a parallel alternate route.
Follow a complete example, including an isolated vertex
Worked example 10.1.4
(A cycle, a bridge, parallel edges and another bridge)
Use vertices 0 through 6 and the following edge order:
| Edge ID | Endpoints | Role in the resulting graph |
|---|---|---|
| First triangle | ||
| First triangle | ||
| First triangle | ||
| Connection to the parallel pair | ||
| One of two parallel edges | ||
| The other parallel edge | ||
| Connection to vertex 5 |
Vertex 6 is isolated. Process roots in increasing order and adjacency entries in input order. The resulting values are:
| Vertex | Discovery time | Completed low value |
|---|---|---|
The triangle edge from 2 to 0 lowers vertex 2 to zero, which propagates to vertex 1. The second parallel edge lowers vertex 4 to discovery time 3. Hence tree edge 4 has equality and is not a bridge. Vertex 5 has no escape, so edge 6 is a bridge. Likewise , making edge 3 a bridge.
The bridge IDs are [3, 6]. The isolated vertex needs its own DFS root but contributes no parent edge to test.
Worked example 10.1.5
(A self-loop and a path)
Take and edges with IDs : , , . At vertex 0 the self-loop entry has ID , which is not a parent edge, and the endpoint is already discovered, so it contributes to , which is already . The tree is the chain with , and , . Edge 2 has and edge 1 has , so both are bridges. The self-loop is never tested as a tree edge and is not a bridge. The bridge IDs are [1, 2].
Replay this same graph to observe each return event and compare physical-edge deletion with two deliberately faulty rules.
An iterative implementation must preserve the return event
The code uses valid integer vertex labels and numbers edges by input position. Each stack frame stores a vertex and its next adjacency position. Advance that position before descending into a child. When the child frame finishes, update the parent and perform the bridge test; this is the iterative equivalent of returning from a recursive DFS call.
def bridge_edges(n, edges):
if n < 0:
raise ValueError("vertex count must be nonnegative")
edges = list(edges)
adjacency = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
if not (0 <= u < n and 0 <= v < n):
raise IndexError("edge endpoint outside the vertex set")
adjacency[u].append((v, edge_id))
adjacency[v].append((u, edge_id))
tin = [-1] * n
low = [-1] * n
parent = [-1] * n
parent_edge = [-1] * n
is_bridge = [False] * len(edges)
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
stack = [(root, 0)]
while stack:
vertex, next_index = stack[-1]
if next_index == len(adjacency[vertex]):
stack.pop()
edge_id = parent_edge[vertex]
if edge_id != -1:
predecessor = parent[vertex]
low[predecessor] = min(low[predecessor], low[vertex])
if low[vertex] > tin[predecessor]:
is_bridge[edge_id] = True
continue
stack[-1] = (vertex, next_index + 1)
neighbor, edge_id = adjacency[vertex][next_index]
if edge_id == parent_edge[vertex]:
continue
if tin[neighbor] != -1:
low[vertex] = min(low[vertex], tin[neighbor])
else:
parent[neighbor] = vertex
parent_edge[neighbor] = edge_id
tin[neighbor] = low[neighbor] = timer
timer += 1
stack.append((neighbor, 0))
bridge_ids = [edge_id for edge_id, flag in enumerate(is_bridge) if flag]
return bridge_ids, tin, low
Every vertex is discovered once. Every undirected edge contributes two adjacency entries, including a loop, and every entry is examined once. Stack operations, low updates and edge flags take constant work per event. The final scan returns bridge IDs in input order without sorting. Total time and space are . Explicit frames also avoid a recursive call-depth limit on long paths.
The returned low values correspond to the particular DFS order, while the set of bridge edges is a property of the graph. Reordering adjacency lists can change discovery and low numbers without changing which edges are bridges.
Remove bridges to expose the forest between robust regions
Theorem 10.1.6
(The bridge forest)
Let have connected components and bridges. Deleting all bridges leaves exactly components, and none of them contains a bridge. Contracting each remaining component to a vertex and restoring the bridges gives a forest.
Proof
(Contracting the bridge-free regions)
Suppose the original graph has connected components and bridges. Delete all the bridges, then find the connected components that remain. Each original bridge is still a bridge when other bridges have already been deleted: removing edges cannot create a new alternate path for it. Every deletion therefore increases the component count by one, giving final components.
Every original nonbridge edge lies on a cycle, and no cycle edge is an original bridge. Those cycles survive the deletions, so the remaining components have no internal bridges.
Contract each remaining component to one vertex and restore the original bridges between these contracted vertices. The resulting graph is a forest. A cycle among contracted vertices would provide an alternate path around each of its bridge edges, after expanding paths inside the contracted components, contradicting their being bridges.
In the worked example, the original and give four regions: , , and . The bridge forest is a three-vertex path together with one isolated vertex.
Counterexample mode
An articulation vertex is a different failure object
Take two triangles sharing vertex 2: one on and one on . Every edge lies on a triangle, so there are no bridges. Deleting vertex 2 and all its incident edges nevertheless separates from , making 2 an articulation vertex.
A bridge test concerns deleting one edge; an articulation test concerns deleting a vertex and its incident edges. The strict bridge comparison does not by itself supply the vertex-deletion algorithm.
Common mistake
(One threshold for both edge and vertex tests)
For a tree edge from to , a bridge needs the strict , because a route back to itself already bypasses the edge. For an articulation vertex , a child separates when , because deleting also destroys a route that returns only to . With edge and two copies of , the equality shows that is not a bridge, yet vertex 1 is an articulation vertex.
Exercises and worked solutions
Quick check
(1. Compare component counts, not a disconnected flag)
A graph already has two connected components. Deleting an edge leaves two components. Is that edge a bridge? What if deletion leaves three components?
Solution · Solution 1
Leaving two means it is not a bridge. Increasing the count to three makes it a bridge. The definition compares before and after; an initially disconnected graph can contain both bridges and nonbridges.
Quick check
(2. Interpret equality correctly)
A DFS tree edge goes from to child , with and . Is it a bridge? What does the equality certify?
Solution · Solution 2
It is not a bridge. Some descendant route reaches through a non-tree edge, avoiding the parent tree edge. Returning to itself is enough; it need not reach a strict ancestor of . This is why the test uses rather than .
Quick check
(3. Preserve a parallel alternate route)
Two vertices have two parallel edges. DFS uses the first as its tree edge. Which adjacency entry is skipped at the child, and how should the second affect its low value?
Solution · Solution 3
Skip only the entry with the first edge's ID. The second remains a non-tree route to the parent and lowers the child's low value to the parent's discovery time. Neither edge is a bridge because the other survives its deletion.
Quick check
(4. Finish the worked bridge tests)
In the seven-vertex example, test tree edges with IDs 3, 4 and 6 using the completed values. Why must the test wait until the child finishes?
Solution · Solution 4
Edge 3 has , so it is a bridge. Edge 4 has , so it is not. Edge 6 has , so it is a bridge. Descendants may discover escape edges that lower the child's value, so testing before its return can use an incomplete value and falsely report a bridge.
Quick check
(5. Separate edge and vertex failures)
Why do two triangles sharing one vertex have no bridges but have an articulation vertex? Would a self-loop ever add a bridge?
Solution · Solution 5
Each edge has an alternate route around its triangle. Removing the shared vertex, however, removes both triangles' only common connection, separating their other vertices. A self-loop never connects distinct vertices and its deletion cannot increase the component count, so it is never a bridge.
Quick check
(6. Count regions after deleting all bridges)
A graph has three original connected components and four bridges. How many components remain after deleting all bridges? Explain why an earlier bridge deletion cannot give a later bridge a new alternate path.
Solution · Solution 6
There are components. Deleting edges can only remove paths, not create them, so each remaining original bridge still lacks an alternate endpoint path. Each deletion increases the count by one. Contracting the seven regions and retaining the four bridges gives a forest with three connected components.