Why Fleury’s Algorithm Produces an Euler Trail

The Correctness Question

Fleury’s algorithm builds an undirected trail one edge at a time. At each step it chooses an unused edge incident to the current vertex, avoiding a bridge whenever another choice is available. The point of the rule is not merely to make a route look promising: it prevents the route from separating itself from unused edges. We will prove that, under the appropriate hypotheses, the algorithm cannot become stuck before every edge has been used.

All graphs in this tutorial are finite and simple. A trail is a walk that does not repeat an edge; it may revisit vertices. A trail is an Euler trail if it uses every edge exactly once. A closed Euler trail is an Euler circuit. The support of a graph is the subgraph consisting of its edges and the vertices incident to those edges; isolated vertices are omitted. A graph with at least one edge has connected support when all its edges lie in one connected component.

We consider an input graph with at least one edge and connected support, in which either every vertex has even degree or exactly two vertices have odd degree. These are the familiar degree conditions for an Euler circuit or an open Euler trail. In the even-degree case, start at any vertex incident to an edge. In the two-odd-vertex case, start at one of the odd-degree vertices. Isolated vertices do not affect the procedure.

We will show that this rule is always executable until there are no unused edges. The key facts are that the unused-edge graph has at most two odd-degree vertices, and, if there are two, one of them is the current vertex. These parity facts restrict how bridges can meet the current vertex.

Parity in the Unused-Edge Graph

Proof. Suppose the algorithm has so far used a trail from its start vertex \(s\) to its current vertex \(x\). If \(s\ne x\), the used edges have odd degree at \(s\) and \(x\), and even degree at every other vertex: each internal visit contributes one used edge entering and one leaving, while the two endpoints have one unmatched incidence. If \(s=x\), the used trail is closed and all its used degrees are even. For each vertex, its original degree is the sum of its used degree and its unused degree. Therefore the parity of the unused degree is the original parity changed exactly at the odd-degree endpoints of the used trail, when those endpoints are distinct.

If all original degrees are even, the unused odd-degree vertices are \(s,x\) when \(s\ne x\), and there are none when \(s=x\). If the original odd vertices are \(s\) and \(t\), then for \(s\ne x\) the unused odd vertices are \(x,t\) when \(x\ne t\), and there are none when \(x=t\). For \(s=x\), they remain \(s,t\). Thus the unused graph has zero or two odd-degree vertices, and in the two-vertex case \(x\) is one of them. \(\square\)

This argument applies to the current unused degrees, not just to the original graph. That distinction matters: bridge choices are assessed after earlier edges have been removed.

Why the Rule Preserves the Remaining Route

Proof. Write \(x\) for the current vertex. If an unused edge \(e\) incident to \(x\) is a bridge, deleting it separates the connected unused-edge support into two sides. Consider the side not containing \(x\). The sum of the unused degrees of the vertices on that side is \(2q+1\), where \(q\) is the number of unused edges entirely within that side: the \(2q\) counts its internal edges twice, and the bridge \(e\) contributes one more incidence. This sum is odd, so the side contains an odd number of odd-degree vertices.

By the preceding lemma, there are either no odd-degree vertices or two, one of which is \(x\). A bridge is therefore impossible if there are no odd-degree vertices. If there are two, the side away from \(x\) must contain the one odd-degree vertex other than \(x\). The sides away from \(x\) belonging to distinct edges incident to \(x\) are disjoint: after removing all edges incident to \(x\), they lie in separate branches of the connected support. Consequently they cannot each contain that same unique odd-degree vertex. At most one unused edge incident to \(x\) is a bridge. If all incident edges are bridges, there is therefore just one. \(\square\)

The connectedness assumption is essential in that proof. It ensures that a bridge separates the support into sides and that distinct branches from \(x\) are disjoint. We next use the lemma to establish the invariant Fleury’s algorithm needs.

Proof. Initially the unused-edge support is connected by hypothesis, and the starting vertex is incident to an edge. Assume the unused-edge support is connected and contains the current vertex. If the algorithm chooses an edge that is not a bridge, deleting it leaves the unused-edge support connected. The new current vertex is the other endpoint of that edge. If unused edges remain but the new current vertex had no unused incident edge, then the deleted edge would have been the only connection from that vertex to the remaining support, so it would have been a bridge. This contradicts the choice.

It remains to consider choosing a bridge. The rule selects a bridge only when there is no nonbridge incident edge. By the preceding lemma, there is then exactly one unused edge incident to the current vertex. Deleting that bridge leaves the old current vertex with no incident unused edge. Since the support before deletion was connected, all remaining edges lie on the other side of the bridge, and their support is connected. The algorithm moves to the other endpoint. If edges remain, that endpoint belongs to their support; otherwise the procedure has already used every edge. This proves the invariant after either type of move. \(\square\)

Fleury’s Algorithm Is Correct

Proof. Each move uses an unused edge incident to the current vertex, so the edges selected form a trail: no edge is repeated, and each new edge continues from the endpoint reached by the preceding move. The connectedness invariant says that whenever unused edges remain, the current vertex lies in their support. It is therefore incident to an unused edge, so the algorithm cannot stop while any edge remains. Each move uses one new edge, and the graph has finitely many edges. Hence after finitely many moves no unused edges remain. The trail uses every edge exactly once, which is the definition of an Euler trail. \(\square\)

The proof also covers the final move. Once no edges remain, the algorithm stops, whether the final vertex is the starting vertex or the other odd-degree vertex. It does not require every vertex to be visited if the input has isolated vertices: only edges must be used, and isolated vertices cannot be part of an edge-traversing step.

Worked Examples

Common Pitfall and Takeaway

A common mistake is to say, “If the chosen edge is a bridge, the algorithm gets stuck.” A bridge can be chosen safely when it is the only unused edge available at the current vertex. In the two-triangle example, after the left triangle has been traversed, \(cd\) is a bridge in the remaining graph, but taking it moves the trail to the side containing all remaining edges. The proof’s connectedness invariant, not a blanket ban on bridges, is what rules out stranding.

Another mistake is to apply the result to a graph with disconnected edge support merely because every degree is even. The disconnected-triangles example shows why the degree condition alone is insufficient. The full argument combines connected support, the residual parity pattern, and the bridge-avoidance rule: nonbridges preserve the connected unused support, while a forced bridge is the unique edge at the current vertex and leaves the remaining edges together on the far side.