Why an Alternate Route Matters
Deleting an edge can disconnect a graph, but the effect depends on whether its endpoints have another route between them. A cycle supplies such a route: if one edge of the cycle is removed, the other edges still connect its endpoints. Conversely, if an edge has no alternate route between its endpoints, removing it separates the part of the graph on one side from the part on the other. This gives a precise test for identifying bridges.
Throughout, graphs are finite, simple and undirected. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A graph is connected if every pair of its vertices is joined by a path. Its connected components are its maximal connected subgraphs; isolated vertices each form a component. We write \(c(G)\) for the number of connected components of \(G\). The graph with no vertices has \(c(G)=0\).
Thus, being a bridge is about the effect of deleting an edge on the number of components. It is not a statement that the whole graph must have been connected beforehand. An edge in one component can be a bridge even when other components are present.
Edge Deletion and Alternate Paths
Fix an edge \(e=uv\), where \(u\) and \(v\) are its endpoints. An alternate \(u\)-\(v\) path means a path from \(u\) to \(v\) that does not use \(e\). The following fact makes the component-count definition practical.
Proof. Let \(C\) be the component of \(G\) containing \(u\) and \(v\). If \(G-e\) still has a \(u\)-\(v\) path, then deleting \(e\) does not disconnect \(C\). To see this, take any two vertices of \(C\), and a path between them in \(G\). If that path uses \(e\), replace \(e\) by the \(u\)-\(v\) path in \(G-e\). The resulting sequence is a walk between the chosen vertices that avoids \(e\). Any finite walk between two vertices contains a path between them: whenever a vertex repeats, delete the part of the walk between two consecutive occurrences of that vertex, and repeat until there is no repetition. Hence every pair of vertices of \(C\) remains connected in \(G-e\). Other components are unchanged, so \(c(G-e)=c(G)\).
Now suppose \(G-e\) has no \(u\)-\(v\) path. Then \(u\) and \(v\) belong to different components after deletion. Every vertex \(x\) of \(C\) belongs to one of those two components. Indeed, choose a path from \(x\) to \(u\) in \(G\). If it avoids \(e\), it connects \(x\) to \(u\) in \(G-e\). If it uses \(e\), it must traverse \(e\) from \(v\) to \(u\), since it ends at \(u\); the part from \(x\) to \(v\) avoids \(e\), connecting \(x\) to \(v\) in \(G-e\). Thus \(C\) splits into exactly two components. All other components stay unchanged, so \(c(G-e)=c(G)+1\). This proves the lemma. \(\square\)
The lemma also explains why searching for a second route is enough: it is not necessary to test all pairs of vertices after deletion. The relevant question is whether the two endpoints of the deleted edge remain connected.
The Cycle Characterization
Proof. Let \(e=uv\). First suppose \(e\) lies on a cycle. Remove \(e\) from that cycle, retaining the sequence of all its other edges. Those edges form a \(u\)-\(v\) path in \(G-e\), because the cycle has no repeated vertices apart from its first and last vertex. By the lemma, deleting \(e\) does not increase the number of components. Therefore \(e\) is not a bridge.
For the reverse direction, suppose \(e\) lies on no cycle. If \(G-e\) had a \(u\)-\(v\) path, that path together with \(e\) would form a cycle: the path has distinct vertices, and adding \(e\) closes it from \(v\) back to \(u\). The path cannot be the single edge \(e\), since it is in \(G-e\); in a simple graph, the resulting cycle therefore has at least three edges. This contradicts the assumption that \(e\) lies on no cycle. Thus \(G-e\) has no \(u\)-\(v\) path, and the lemma shows that deleting \(e\) increases the number of components. Hence \(e\) is a bridge. \(\square\)
The two directions give a useful distinction. To show an edge is not a bridge, it suffices to exhibit one cycle containing it. To show it is a bridge, one must establish that no cycle contains it—for example, by showing that its endpoints have no alternate path.
Worked Applications
Worked Example: A Cycle with Tree-Like Branches
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,bc,ca,cd,de,ef,cg\}\). The edges \(ab,bc,ca\) form a triangle, and the other edges form branches attached at \(c\). Identify all bridges.
The triangle edges are not bridges: for \(ab\), the other two edges \(ac,cb\) give an alternate path from \(a\) to \(b\); for \(bc\), the edges \(ba,ac\) give an alternate path from \(b\) to \(c\); and for \(ca\), the edges \(cb,ba\) give an alternate path from \(c\) to \(a\). Each edge lies on the cycle \(a,b,c,a\).
Each remaining edge lies on no cycle. One way to check this is to remove it and see that its endpoints have no alternate route. Removing \(cd\) separates \(\{d,e,f\}\) from \(\{a,b,c,g\}\); removing \(de\) separates \(\{e,f\}\) from \(\{a,b,c,d,g\}\); removing \(ef\) separates \(\{f\}\) from \(\{a,b,c,d,e,g\}\); and removing \(cg\) separates \(\{g\}\) from \(\{a,b,c,d,e,f\}\). Thus \(cd,de,ef,cg\) are bridges.
Check: The original graph is connected, so \(c(G)=1\). Deleting any of \(cd,de,ef,cg\) gives \(c(G-e)=2\), as the displayed vertex groups show. Deleting any triangle edge leaves the graph connected because the other two triangle edges still connect \(a,b,c\), and all the branches remain attached at \(c\). The cycle criterion and the component counts agree.
Worked Example: Every Edge of a Path Is a Bridge
Let \(G=(V,E)\) be the path with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). There is no cycle: each edge joins consecutive vertices in the displayed linear order, and moving along edges cannot return to a previous vertex without reversing direction and repeating an edge. The theorem therefore says that every edge is a bridge.
The component counts can also be checked directly. Before deletion, \(c(G)=1\). Deleting \(12\) gives components on \(\{1\}\) and \(\{2,3,4,5\}\), so \(c(G-12)=2\). Deleting \(23\) gives components on \(\{1,2\}\) and \(\{3,4,5\}\), so \(c(G-23)=2\). Deleting \(34\) gives components on \(\{1,2,3\}\) and \(\{4,5\}\), so \(c(G-34)=2\). Deleting \(45\) gives components on \(\{1,2,3,4\}\) and \(\{5\}\), so \(c(G-45)=2\).
Check: Each of the four deletions changes the component count from \(1\) to \(2\). There are four edges, and all four are bridges, matching the fact that none lies on a cycle.
Worked Example: A Cycle with a Chord and an Isolated Vertex
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,z\}\) and \(E=\{12,23,34,45,51,13\}\). The vertices \(1,2,3,4,5\) form a 5-cycle, \(13\) is a chord, and \(z\) is isolated. Determine whether any edge is a bridge.
The five cycle edges each lie on the cycle \(1,2,3,4,5,1\). The chord \(13\) lies on the cycle \(1,2,3,1\). Thus every edge lies on a cycle, so the theorem says that none is a bridge. For a direct alternate-path check, the cycle edges \(12,23,34,45,51\) have alternate routes along the rest of the 5-cycle, of lengths \(4,4,4,4,4\), respectively. The chord \(13\) has the alternate path \(1,2,3\), of length \(2\).
Check: The initial graph has two components: the component on \(\{1,2,3,4,5\}\) and the isolated vertex \(\{z\}\), so \(c(G)=2\). For every edge, the alternate route just given keeps the five-vertex component connected after deletion; the isolated vertex is unchanged. Therefore \(c(G-e)=2\) for every \(e\in E\), confirming that no edge is a bridge even though the graph is disconnected.
A Common Mistake
Wrong claim: “The edge \(cd\) in the first example is not a bridge because \(c\) lies on the triangle.” This confuses an edge incident to a cycle vertex with an edge lying on a cycle. The edge \(cd\) is not one of the triangle's edges, and there is no route from \(c\) to \(d\) that avoids \(cd\). Deleting \(cd\) separates \(\{d,e,f\}\) from the rest of the graph, so \(cd\) is a bridge. The test is whether the edge itself lies on a cycle, equivalently whether its endpoints have an alternate path—not whether one endpoint belongs to some cycle.
Another useful check is to keep the component count global. In a disconnected graph, deleting a bridge raises the total number of components by one; it does not require that the original graph had just one component. The isolated vertex in the third example contributes to both counts but does not affect whether any of the other edges is a bridge.
Why the Criterion Is Useful
The cycle criterion lets us read structural information directly from a graph. Edges inside cycles have redundancy: deleting one leaves its endpoints connected by the rest of the cycle. Edges in tree-like branches have no such route and are bridges. This does not mean that every edge in a region that “looks tree-like” is automatically a bridge; the precise test remains whether the edge belongs to any cycle in the graph.
For an individual edge \(uv\), the reasoning can be organized as follows: try to find a \(u\)-\(v\) path that avoids the edge. If one exists, adding the edge to that path produces a cycle, and the edge is not a bridge. If no such path exists, deleting the edge separates its endpoints and the edge is a bridge. The result applies component by component, including when the graph has isolated vertices or is empty; in the empty graph there are no edges to test.
Check Your Understanding
For each question, justify your answer using an alternate path, a cycle, or the change in component count.
- Can a graph contain a bridge and also contain a cycle? Give an example by specifying its vertex and edge sets.
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\), identify the bridges and verify the component counts after deleting them.
- Explain why an edge on a cycle cannot be a bridge, even if deleting it changes the number of edges in that cycle.
- Suppose \(G\) has three components and \(e\) is a bridge in one of them. What is \(c(G-e)\), and why?
- Give a graph with an isolated vertex and at least one bridge, and explain why the isolated vertex does not alter the bridge test for that edge.