Mathwords logoMathwords

Fleury's Algorithm — Definition & Example

Fleury's algorithm is a step-by-step method for tracing every edge of a graph exactly once. At each step you avoid crossing a bridge, an edge whose removal would cut off untraveled edges, unless you have no other choice.

Let GG be a connected graph in which every vertex has even degree, or exactly two vertices have odd degree. Start at any vertex in the first case, or at an odd vertex in the second. Repeatedly traverse an edge incident to the current vertex and delete it. Choose an edge that is not a bridge of the remaining graph (ignoring isolated vertices) whenever such an edge exists. The process ends when no edges remain, and the sequence of traversed edges is an Euler circuit or Euler trail of GG. With a naive bridge test at each step, the running time is O(∣E∣2)O(|E|^2).

Worked Example

Problem: A graph has vertices A, B, C, D, E, F and 7 edges: AB, BC, CD, DA (a square) and CE, EF, FC (a triangle). The two cycles share vertex C. Use Fleury's algorithm starting at A to find an Euler circuit.
Step 1: Check that an Euler circuit exists. The graph is connected. C has degree 4, and every other vertex has degree 2, so all degrees are even. The degree sum equals twice the number of edges.
2+2+4+2+2+2=14=2×72+2+4+2+2+2 = 14 = 2 \times 7
Step 2: At A, both AB and AD lie on the square cycle, so neither is a bridge. Take AB. At B, the only remaining edge is BC. Removing it would isolate B, so it is a bridge, but Fleury's rule allows a bridge when there is no alternative. Take BC.
A→B→CA \to B \to C
Step 3: At C you have three choices: CD, CE, CF. The remaining edges are the path C–D–A and the triangle C–E–F. Deleting CD would cut D and A off from E and F, so CD is a bridge. CE is not a bridge, so take it.
A→B→C→EA \to B \to C \to E
Step 4: Every move from here is forced, because each vertex has only one remaining edge: EF, then FC, then CD, then DA.
A→B→C→E→F→C→D→AA \to B \to C \to E \to F \to C \to D \to A
Answer: The Euler circuit is A → B → C → E → F → C → D → A. It uses all 7 edges exactly once and returns to A.

Why It Matters

Snowplow routes, mail delivery, and street-sweeping schedules all try to cover every street once with no repeats. That is an Euler circuit problem, and Fleury's algorithm is the standard hand method taught in discrete math and liberal-arts math courses. Faster methods such as Hierholzer's algorithm are used for large graphs.

Common Mistakes

Mistake: Taking a bridge when a non-bridge edge is available, such as choosing CD at vertex C in the example.
Correction: Taking CD gives A → B → C → D → A, and you are stuck at A while CE, EF, and FC are still untraveled. Before each move, ask whether deleting the edge would separate untraveled edges from you. Cross a bridge only when it is your last option.

Related Terms