What is a bridge?
Definition 3.1.1
(Bridge of a multigraph)
In a finite undirected multigraph, edges have distinct IDs; parallel edges and self-loops are allowed. An edge is a bridge if deleting that one edge increases the number of connected components. This definition applies to disconnected graphs too.
A self-loop is never a bridge, and neither of two parallel edges is a bridge: after deleting one, the other still joins the same endpoints.
Depth-first search (DFS) can find all bridges in linear time, but an implementation must distinguish the edge used to enter a vertex from other edges to the same parent. We count vertices and edge IDs, not just endpoint pairs.
Concept lensStructural
A bridge is an edge on no cycle
Equivalently, an edge is a bridge exactly when it lies on no cycle. A cycle through is together with a route between its endpoints that avoids ; two parallel edges form a cycle of length two and a loop is a cycle of length one. The low-link test is a way of detecting such a cycle for a tree edge.
Discovery time and reachable ancestors
Run DFS from every still-unvisited vertex. Set to a distinct positive discovery time and initialize . For a tree edge from to newly visited , finish the recursive search at , then set
For any other incident edge to an already visited vertex , except the single edge ID used to enter , set . A self-loop can only compare the value with and cannot lower it. An edge to an already discovered descendant cannot lower it either, because .
Definition 3.1.2
(Low-link value)
After returning from , is the smallest discovery time reachable by going down zero or more DFS tree edges within 's subtree and then using at most one non-tree edge to an ancestor (including itself).
The initialization permits using no non-tree edge. The update over children propagates their minima; the visited-neighbor updates account for non-tree edges. In an undirected DFS, a non-tree edge joins an ancestor and a descendant, or is a loop: otherwise the first explored endpoint would have discovered the other before finishing, making it a descendant.
The bridge criterion
Theorem 3.1.3
(Low-link bridge criterion)
Let be the set of bridges. For a DFS tree edge , where is the parent of ,
Every non-tree edge, including every self-loop, is not a bridge.
Proof
(A return route versus a lone connection)
If , either or a descendant of has a non-tree edge to or an ancestor of . Follow zero or more tree edges down to that endpoint, take the non-tree edge and, if needed, follow tree edges back to . This supplies a route from to avoiding , so deleting does not disconnect its endpoints.
Conversely, suppose . Every non-tree edge leaving the subtree of goes to an ancestor of other than itself, that is, to or an ancestor of , and any such edge would give ; so there is none. By the DFS property there is no edge from that subtree to a separate finished subtree. Thus is its only edge to the rest of its DFS component, and deleting it increases the component count.
A non-tree edge is never a bridge: its endpoints already have a tree path between them, or it is a loop.
Proof X-ray
Strict inequality and the entering edge ID
The non-routine step is the converse, and it uses two facts about undirected DFS: a non-tree edge joins an ancestor and a descendant, and there are no edges between separate finished subtrees. Together they show that the only edges leaving the subtree of go up to ancestors, so sees all of them. The inequality must be strict: an edge back to itself gives and is an alternative route. The parent edge must be skipped by its ID, not by its endpoint: the single entering edge is the tree edge being tested, whereas a parallel copy is a genuine return route.
The parallel-edge case explains why the parent edge must be skipped, not every edge to the parent vertex. If enters by one edge and a second edge also joins them, that second ID gives .
Counterexample mode
Skipping every edge to the parent vertex
A tempting implementation skips every edge whose other endpoint is the parent vertex. Take vertices and two edges and joining them. Start at with , and enter by edge , so . At , edge is skipped because it leads to the parent vertex, so and edge is reported as a bridge. It is not: deleting edge leaves edge , and the graph is still connected. Skipping only the single ID used to enter gives and the correct answer, no bridge.
Worked DFS traces
Worked example 3.1.4
(A six-vertex multigraph with a loop)
Use vertices and the following edge IDs, with adjacency lists processed in increasing ID order:
| ID | Endpoints | ID | Endpoints |
|---|---|---|---|
| 1 | 5 | ||
| 2 | 6 | ||
| 3 | 7 | ||
| 4 | 8 |
Start DFS at with discovery times beginning at . The tree visits in that order. The second edge lowers to , while edge lowers to and propagates that value through and . The loop at changes no minimum.
| Vertex | ||||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 1 | 2 | 2 | 2 | 6 |
Only edge is a bridge: . For tree edge , equality correctly rules out a bridge.
Worked example 3.1.5
(Parallel edges, a loop and a pendant vertex)
Take vertices and edges , , , . Start at with and enter by edge , so . At we skip edge (the entering ID); edge reaches the visited vertex and sets ; the loop compares with and changes nothing; edge enters with , and because its only other edge is the entering one. Back at , . The tests are (false) for edge , and (true) for edge . So only edge is a bridge, which agrees with deleting each edge by hand.
Worked example 3.1.6
(A tree and an isolated vertex)
Let the edges be and , with a fourth vertex having no edges. DFS from gives for and no non-tree edges, so . Then and , so both edges are bridges. DFS must also be started from the still-unvisited vertex ; it finds no tree edge, so it adds no bridge.
Common mistake
(Using at-least instead of strictly greater)
Testing is the articulation-vertex condition, not the bridge condition. In the six-vertex trace it would flag tree edge , since , although edge gives a second route from back to . For a bridge the inequality must be strict.
Common mistake
(Starting DFS from one vertex only)
For a graph with the two components joined by one edge and joined by one edge, a DFS from finds only the first bridge. Run the search from every still-unvisited vertex, as the definition of a bridge applies to each component.
Cost
Theorem 3.1.7
(Linear running time of the bridge search)
With adjacency lists, the DFS bridge search takes time and space for the graph and arrays; a recursive implementation can additionally use call-stack space.
Proof
(Count the incidences)
Each vertex is visited once, and the search is restarted at most once per vertex. Each edge appears in the adjacency lists of its endpoints, at most twice (a loop appears twice at one vertex), and each appearance is examined once with a constant-time comparison or update. The total is . The arrays and have length , and the graph itself needs space; the recursion depth is at most .
Store and compare edge IDs even if adjacency lists are reordered: the particular discovery numbers may change, but the set of bridges does not.
Exercises
Quick check
(In the six-vertex graph, delete edge 6 before running DFS. Which edges are bridges now? Explain without relying only on old low values.)
What shape does the part on have after the deletion?
Solution · Answer
Edges 3, 4, 5 and 7 are bridges. The part is then a path; deleting any one of those four edges separates it. Edges 1 and 2 remain parallel and are not bridges; the loop is not a bridge.
Quick check
(What happens to bridge status when the self-loop at is deleted? Why?)
Can a loop help connect two different vertices?
Solution · Answer
No other edge changes status: a loop cannot connect distinct vertices or provide an alternative path between them.
Quick check
(Two vertices are joined by three distinct parallel edges. How many are bridges? What mistake can occur if a DFS skips all edges to the parent vertex?)
Delete one edge and see what remains.
Solution · Answer
None are bridges. Skipping all edges to the parent can discard both alternative parallel edges and make the tree edge appear to have no return route.
Quick check
(For the triangle with edges , , , DFS from in that edge order. Give and and the bridges.)
Edge is the only non-tree edge.
Solution · Answer
The tree is with . At the edge reaches , so , and propagating gives and . The tests are and , both false. There are no bridges, as expected for a cycle.