Bridges During an Euler Trail
Fleury’s algorithm chooses edges one at a time to build an Euler trail: a trail that uses every edge exactly once. When bridges are present, the crucial question is not simply whether an edge was a bridge in the original graph. It is whether that edge is a bridge among the edges that remain unused at the moment it is considered. Using a bridge too early can leave unused edges on the wrong side of it.
Throughout, graphs are finite, simple and undirected. A bridge of a graph is an edge whose deletion separates its endpoints into different connected components. A trail uses no edge more than once; vertices may repeat. We apply Fleury’s algorithm to a connected graph that has an Euler trail, starting at an odd-degree vertex if there are two odd-degree vertices, or at any vertex with an incident edge if all degrees are even. These are the usual conditions for an undirected Euler trail or circuit.
Testing an edge against the remaining graph matters because earlier choices can change which edges are bridges. Vertices with no unused incident edges do not affect the test: what matters is whether the endpoints of a candidate edge can still be connected by other unused edges. A bridge is sometimes the only available edge at the current vertex. In that case the rule permits it; postponing it is not an option.
Why the Rule Avoids a Premature Crossing
Proof. Let \(xy\) be a bridge in the remaining graph, and suppose an Euler-trail completion starts with \(xy\). Since \(xy\) is a bridge, deleting it separates \(x\) and \(y\); let \(A\) be the side containing \(x\), and \(B\) the side containing \(y\). If another unused edge is incident to \(x\), that edge lies in \(A\), because \(xy\) is the only remaining edge between the two sides. After taking \(xy\), the trail is in \(B\). It cannot return to \(A\): the only edge between the sides is \(xy\), and a trail cannot use that edge a second time. It therefore cannot use the other unused edge incident to \(x\), contradicting the requirement that the completion use every remaining edge. So a completion cannot begin with \(xy\). \(\square\)
This proposition explains why crossing a bridge while another unused edge is available can strand edges. It also explains the exception in the rule: when there is only one unused edge at the current vertex, there is no alternative to postpone it.
The proposition concerns the existence of a valid completion; it does not by itself prove that every non-bridge choice preserves one. The earlier result that Fleury’s algorithm produces an Euler trail supplies that guarantee. Here we focus on applying the rule accurately: identify the remaining edges, test candidate edges in that graph, and update the test after each choice.
Tracing the Rule on Graphs with Bridges
Worked Example: Two Triangles Joined by a Bridge
Let \(G=(V,E)\) be the undirected graph with \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,bc,ca,cd,de,ef,fd\}\). The edges \(ab,bc,ca\) form one triangle, \(de,ef,fd\) form another, and \(cd\) joins them. The degrees are \(\deg(c)=3\), \(\deg(d)=3\), and \(\deg(a)=\deg(b)=\deg(e)=\deg(f)=2\). Thus \(c,d\) are the two odd-degree vertices; start at \(c\) and finish at \(d\).
Initially, \(cd\) is a bridge: deleting it separates the triangle \(abc\) from the triangle \(def\). The edges \(ca\) and \(cb\) are not bridges, since the other two edges of the triangle still connect their endpoints. The choices proceed as follows.
| Current vertex | Unused incident edges | Bridge status and choice |
|---|---|---|
| \(c\) | \(ca,cb,cd\) | \(ca,cb\) are not bridges; \(cd\) is a bridge. Choose \(ca\). |
| \(a\) | \(ab\) | Only choice: take \(ab\). |
| \(b\) | \(bc\) | Only choice: take \(bc\). |
| \(c\) | \(cd\) | Only choice: take \(cd\). |
| \(d\) | \(de,df\) | Neither edge is a bridge in the remaining triangle. Choose \(de\). |
| \(e\) | \(ef\) | Only choice: take \(ef\). |
| \(f\) | \(fd\) | Only choice: take \(fd\). |
The resulting trail is \(c,a,b,c,d,e,f,d\). The tempting alternative at the first step is \(cd\). If we take it immediately, the trail moves from the left triangle to the right triangle while the edges \(ca,ab,bc\) are still unused. The only edge between the triangles is \(cd\), and it cannot be reused, so those three edges could no longer be reached.
Check: The trail uses \(ca,ab,bc,cd,de,ef,fd\), each exactly once, so it uses all seven edges. It starts at \(c\) and ends at \(d\), the two odd-degree vertices.
Worked Example: A Triangle with a Pendant Path
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,ad,de\}\). The edge \(ad\) joins the triangle \(abc\) to the path \(a,d,e\); in particular, deleting \(ad\) separates \(d,e\) from \(a,b,c\). The degrees are \(\deg(a)=3\), \(\deg(e)=1\), and \(\deg(b)=\deg(c)=\deg(d)=2\). Start at \(a\) and finish at \(e\).
At \(a\), the unused edges are \(ab,ac,ad\). The edge \(ad\) is a bridge, while \(ab\) and \(ac\) are not: the other two triangle edges connect their endpoints. Choose \(ab\). At \(b\), only \(bc\) remains incident; at \(c\), only \(ca\) remains incident. Returning to \(a\), the only unused incident edge is the bridge \(ad\), so it is now forced. At \(d\), take the only remaining incident edge \(de\).
The complete trail is \(a,b,c,a,d,e\). Its edge order is \(ab,bc,ca,ad,de\): all five specified edges appear once. The trail starts at the odd-degree vertex \(a\) and ends at the odd-degree vertex \(e\). If \(ad\) were chosen first, the two triangle edges not yet used would be left behind, with no unused connection back to them.
Worked Example: An Edge Becomes a Bridge After a Choice
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,ac,bc,ad,bd\}\). The triangles \(abc\) and \(abd\) share the edge \(ab\). Their degrees are \(\deg(a)=3\), \(\deg(b)=3\), \(\deg(c)=2\), and \(\deg(d)=2\), so start at \(a\) and finish at \(b\). Initially, no edge is a bridge: each edge lies on at least one of the two triangles.
At \(a\), choose \(ac\), which is not a bridge in the original graph. The remaining edges are now \(ab,bc,ad,bd\). In this remaining graph, \(bc\) is a bridge: it is the only remaining edge incident to \(c\), so deleting it disconnects \(c\) from \(b\). The trail is currently at \(c\), where \(bc\) is the only available edge, so take it. This is an example of a bridge that has arisen in the remaining graph even though it was not a bridge initially.
Now at \(b\), the remaining incident edges are \(ab\) and \(bd\). Neither is a bridge because the remaining edges \(ab,ad,bd\) form a triangle, so choose \(bd\). At \(d\), only \(da\) remains; take it. At \(a\), only \(ab\) remains; take it. The complete trail is \(a,c,b,d,a,b\).
Check: The trail uses \(ac,bc,bd,ad,ab\), which is exactly the five-edge set \(E\). It starts at \(a\) and ends at \(b\), the two odd-degree vertices.
Updating Bridge Status Correctly
In the first two examples, an important bridge was already present in the original graph. In the third, the edge \(bc\) became a bridge only after \(ac\) was used. Therefore, memorizing a list of bridges at the start is not enough. After each choice, the unused-edge set changes, and the bridge test must be made on that updated set.
A practical way to test a candidate edge \(uv\) is to temporarily delete it from the remaining graph and ask whether \(u\) and \(v\) are still connected using unused edges. If they are connected, \(uv\) is not a bridge; if they are disconnected, it is a bridge. This is a connectivity test, not a test of whether \(uv\) was a bridge in the original graph.
Only edges joining the current vertex to a neighbor and not yet used are candidates.
For each candidate, check whether its endpoints remain connected after that edge is deleted.
If every available edge is a bridge, take one; if exactly one edge is available, it is forced.
Mark the chosen edge used, move to its other endpoint, and retest using only the edges still unused.
Common Pitfalls
Using the original bridge status throughout. In the third example, \(bc\) is not initially a bridge because it lies on the triangle \(abc\). After \(ac\) has been used, \(bc\) is a bridge among the remaining edges. A calculation that continues to label \(bc\) “not a bridge” because of the original triangle ignores that \(ac\) is no longer available.
Never taking a bridge. The rule does not forbid bridges. In the first example, after the left triangle has been traversed, \(cd\) is the only unused edge at \(c\); it must be taken. In the second example, the bridge \(ad\) is likewise forced after the triangle is complete. The instruction is to avoid a bridge when a non-bridge alternative is available, not to avoid bridges altogether.
Checking only whether a choice looks safe locally. A candidate may lead to the next vertex but still separate unused edges from the trail. For instance, taking \(cd\) first in the two-triangle example is a legal first step along an edge, but it cannot be part of a trail using every edge exactly once. The bridge test is precisely what detects this danger.
Check Your Understanding
For each question, use the graph of unused edges at the stated stage, rather than assuming bridge status stays fixed.
- In the graph on \(\{a,b,c,d,e,f\}\) with edges \(ab,bc,ca,cd,de,ef,fd\), why is choosing \(cd\) first invalid for an Euler trail starting at \(c\)?
- In the graph on \(\{a,b,c,d,e\}\) with edges \(ab,bc,ca,ad,de\), which edge is forced after the triangle has been traversed, and why?
- In the graph on \(\{a,b,c,d\}\) with edges \(ab,ac,bc,ad,bd\), identify an edge that is not initially a bridge but becomes a bridge after \(ac\) is used.
- State the test for deciding whether an unused edge is a bridge at the current stage.
- Explain why Fleury’s rule permits choosing a bridge when it is the only unused edge incident to the current vertex.