The Choice Fleury’s Rule Makes
An Euler trail uses every edge of a graph exactly once. When several unused edges leave the current vertex, choosing one without considering the rest of the graph can make it impossible to continue using all the edges. Fleury’s rule avoids this danger by delaying bridges whenever there is another option. The important detail is that bridge status must be checked in the graph of unused edges, so it can change as the trail is constructed.
All graphs in this tutorial are finite and simple, and undirected. A trail is a walk with no repeated edges; an Euler trail is a trail that uses every edge exactly once. An Euler trail whose first and last vertices are the same is an Euler circuit. A bridge is an edge whose deletion increases the number of connected components. At a particular step, the relevant graph consists of the original vertices and only the edges not yet used.
We consider a graph with at least one edge that is already known to have an Euler trail. Start at an appropriate endpoint: if there are two odd-degree vertices, start at one of them; if all degrees are even, start at any vertex incident to an edge. These conditions are standard prerequisites for the Euler-trail construction; Fleury’s rule specifies how to choose the successive edges.
Thus, “avoid bridges” is a preference, not an absolute prohibition. Sometimes every available edge is a bridge, and the rule requires taking one. The bridge test also needs to be repeated after each move: deleting an edge changes the graph in which the next test is made.
Why the Rule Delays Bridges
Proof. By definition, deleting a non-bridge does not increase the number of connected components. Since \(H\) is connected, it has one component, so \(H-e\) also has one component. \(\square\)
This lemma gives the local reason for preferring a non-bridge: when the unused edges are connected, taking a non-bridge leaves their graph connected after the chosen edge is removed. By contrast, if \(e=uv\) is a bridge of connected \(H\), deleting it separates \(H\) into components, one containing \(u\) and the other containing \(v\). If the trail traverses \(e\) from \(u\) to \(v\), it cannot traverse \(e\) again to return to the \(u\)-side. Any unused edges left there would be stranded.
This explains why a bridge is risky, but it does not mean that every bridge must be postponed until the very last move. The route must also be able to leave the current vertex, and in some situations every available edge is a bridge. Fleury’s rule handles that situation by allowing the forced choice. The local observation alone is not a complete proof that the algorithm always succeeds; the global correctness argument concerns how the trail and the remaining edges fit together over all the steps.
Applying the Rule Step by Step
Worked Example: Two Triangles Joined by a Bridge
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,bc,ca,cd,de,ef,fd\}\). The edges \(ab,bc,ca\) form one triangle, the edges \(de,ef,fd\) form another, and \(cd\) joins them. The vertices \(c,d\) have degree \(3\), while \(a,b,e,f\) have degree \(2\). We start at \(c\), one of the two odd-degree vertices.
Initially, \(cd\) is a bridge: deleting it separates the two triangles. The edges \(ca\) and \(cb\) are not bridges because each lies on a triangle. Fleury’s rule therefore chooses \(ca\) or \(cb\); choose \(ca\). At each step below, the bridge status refers to the unused edges at the start of that step.
| Step | Current vertex | Unused incident choices | Choice |
|---|---|---|---|
| 1 | \(c\) | \(ca,cb\) are non-bridges; \(cd\) is a bridge | \(ca\) |
| 2 | \(a\) | Only \(ab\) remains incident to \(a\) | \(ab\) |
| 3 | \(b\) | Only \(bc\) remains incident to \(b\) | \(bc\) |
| 4 | \(c\) | Only \(cd\) remains incident to \(c\) | \(cd\) |
| 5 | \(d\) | \(de,df\) are non-bridges in the remaining triangle | \(de\) |
| 6 | \(e\) | Only \(ef\) remains incident to \(e\) | \(ef\) |
| 7 | \(f\) | Only \(fd\) remains incident to \(f\) | \(fd\) |
The resulting route is \(c,a,b,c,d,e,f,d\). In steps 2 and 3 the indicated choices are forced: after using \(ca\), the only unused edge at \(a\) is \(ab\); after using \(ab\), the only unused edge at \(b\) is \(bc\). When the route returns to \(c\), the only unused edge there is \(cd\), so taking that bridge is also forced.
Check: The route uses, in order, \(ca,ab,bc,cd,de,ef,fd\). These are exactly the seven edges in \(E\), each appearing once. The route begins at \(c\) and ends at \(d\), as expected for the two odd-degree vertices.
Notice how the bridge changes roles in the construction: it is avoided at the start because there are non-bridge choices, but taken later when it is the only unused edge available at the current vertex. Bridge status and the available choices must be read from the current stage, not from an imagined fixed route through the original graph.
Worked Example: An Euler Circuit in a 4-Cycle
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Every vertex has degree \(2\), so we can start at \(1\). Initially none of the four edges is a bridge: deleting any one edge leaves a path connecting all four vertices. Choose \(12\).
After \(12\) is used, the unused edges are \(23,34,41\), which form the path \(2,3,4,1\). Each remaining edge is now a bridge in the graph of unused edges: deleting any one of them disconnects that path. The choices are forced as the route proceeds:
| Step | Current vertex | Unused incident edge | Choice |
|---|---|---|---|
| 1 | \(1\) | \(12\), initially a non-bridge | \(12\) |
| 2 | \(2\) | \(23\), now a bridge | \(23\) |
| 3 | \(3\) | \(34\), now a bridge | \(34\) |
| 4 | \(4\) | \(41\), now a bridge | \(41\) |
The route is \(1,2,3,4,1\). After the first move, there is no competing unused edge at the current vertex, so Fleury’s rule allows the bridge choice at each subsequent step.
Check: The route traverses \(12,23,34,41\), exactly the four edges listed in \(E\), and returns to its starting vertex. It is therefore an Euler circuit.
When a Bridge Is the Only Choice
Worked Example: A Cycle with a Pendant Path
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,cd,de\}\). The triangle \(a,b,c\) is attached to the path \(c,d,e\). The degrees of \(c\) and \(e\) are \(3\) and \(1\), respectively; \(a,b,d\) each have degree \(2\). Start at \(e\), an odd-degree vertex.
At \(e\), the only unused incident edge is \(de\), which is a bridge. The rule requires taking it. At \(d\), the only unused incident edge is \(dc\), also a bridge at this stage, so take that as well. At \(c\), the remaining edges \(ca,cb,ab\) form a triangle, and neither \(ca\) nor \(cb\) is a bridge. Choose \(ca\), then follow the forced remaining edges \(ab\) and \(bc\).
| Step | Current vertex | Unused incident choices | Choice |
|---|---|---|---|
| 1 | \(e\) | Only \(de\), a bridge | \(de\) |
| 2 | \(d\) | Only \(dc\), a bridge | \(dc\) |
| 3 | \(c\) | \(ca,cb\) are non-bridges | \(ca\) |
| 4 | \(a\) | Only \(ab\) remains incident to \(a\) | \(ab\) |
| 5 | \(b\) | Only \(bc\) remains incident to \(b\) | \(bc\) |
The route is \(e,d,c,a,b,c\). The two bridge edges are taken first because the starting vertex has no alternative; the triangle is then traversed without repeating an edge.
Check: The route uses \(ed,dc,ca,ab,bc\), which are exactly the five edges of \(E\), each once. It starts at \(e\) and ends at \(c\); these are the two odd-degree vertices.
Common Mistakes and Practical Checks
Testing the original graph instead of the remaining graph. In the 4-cycle example, \(23\) is not a bridge in the original graph, but it is a bridge after \(12\) has been used. A wrong calculation would say, “Choose \(23\), because it is not a bridge of \(G\).” The correction is to delete already-used edges first and test \(23\) in the residual graph. At that stage, the remaining edges form a path, and deleting \(23\) disconnects it.
Treating every bridge as forbidden. A bridge may be the only unused edge incident to the current vertex, as at \(e\) in the pendant-path example. The rule does not say to stop or to choose an unavailable non-bridge; it says to choose a non-bridge if one is available, and otherwise to take an available bridge.
Forgetting to use every edge. Reaching a previously visited vertex does not end the algorithm. The route ends only when the prescribed construction has used every edge. For a proposed result, check that consecutive vertices are adjacent, no edge is repeated, and every edge in the specified edge set occurs once. The route may repeat vertices; an Euler trail is required to avoid repeated edges, not repeated vertices.
Fleury’s rule is useful as a transparent hand method because it makes each local choice explicit. Its main bookkeeping task is maintaining the unused-edge graph and retesting bridges in that graph. On a small graph, a table of current vertices, unused choices, and bridge statuses makes the rule auditable. The examples also show its scope: it guides a construction when an Euler trail is known to exist; simply following the local preference is not a substitute for checking the graph’s Euler-trail conditions.
Check Your Understanding
For each question, evaluate bridge status in the graph of currently unused edges, not automatically in the original graph.
- In the 4-cycle example, after edge \(12\) is used, why is \(23\) a bridge in the remaining graph?
- State Fleury’s rule in a way that makes clear what to do if all unused edges at the current vertex are bridges.
- In the graph with edges \(ab,bc,ca,cd,de\), which edge must be taken first when starting at \(e\), and why?
- Can a vertex appear more than once in an Euler trail? Explain the difference between the restriction on vertices and the restriction on edges.
- Why is it incorrect to decide at the beginning which edges are bridges and use those same classifications throughout the construction?