Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

A walkthrough of Fleury's algorithm for Eulerian paths

In the late 18th century, the city of Königsberg posed a puzzle that launched an entire branch of mathematics. Residents wondered whether they could walk across all seven of the city's bridges exactly once without retracing a step. Leonhard Euler solved the puzzle by abstracting the city into a graph, and in doing so, he gave the world the concept of an Eulerian path. Today, this same idea powers software for route planning, network verification, and DNA fragment assembly, and the Fleury algorithm remains one of the clearest ways to construct such paths by hand or in code.

Before diving into the algorithm itself, it helps to fix the vocabulary. A graph consists of vertices (sometimes called nodes) connected by edges (or links). An Eulerian path traverses every edge of a graph exactly once. When the path returns to its starting vertex, it becomes an Eulerian circuit or Eulerian tour. Fleury's algorithm, published by the French mathematician M. Fleury in 1883, builds these structures step by step while respecting a subtle rule about which edges may be crossed.

The mathematical heritage of Eulerian paths

Euler's original insight was conditional on the degree of each vertex, where degree means the count of edges touching that point. If every vertex in a connected graph has an even degree, then an Eulerian circuit exists. If exactly two vertices have odd degree, then an Eulerian path exists and must start at one odd-degree vertex and end at the other. If more than two vertices have odd degree, no such path can be drawn.

These conditions are easy to verify. Walk through the vertices, count the edges meeting at each, and compare the totals. For a small graph drawn on paper, this works in seconds. For a graph with millions of vertices, the same counting is delegated to a program, but the rule has not changed since the 1700s. Many computer science students at the University of Melbourne first encounter this check in second-year discrete mathematics, and it remains one of the most exam-tested theorems in the field.

The wording matters as well. Tutors in Sydney and Brisbane universities often stress that "connected" is a prerequisite, since a disconnected graph by definition cannot have a single path that reaches every edge. Once those two cornerstones are clear, the algorithm itself becomes much easier to internalise.

Determining whether a path exists

Before running Fleury's algorithm, programmers should always confirm that an Eulerian path could exist. The degree check is fast: a single pass over the adjacency list gives the count for every vertex. If that pass returns more than two odd-degree vertices, the algorithm should bail out immediately and report that no traversal is possible.

Consider a small bridge network linking three precincts of central Melbourne. Suppose vertex A connects to B and C, vertex B connects to A, C, and D, vertex C connects to A and B, and vertex D connects only to B. The degrees are A:2, B:3, C:2, D:1, which is three odd-degree vertices. Even though the graph is connected, no Eulerian path can traverse every edge exactly once. Adding a single extra edge from D to C would change D's degree to 2, leaving only B as odd, and a path becomes possible.

This pre-check saves real work. Fleury's algorithm in its naive form runs in quadratic time with respect to the number of edges, and feeding it an impossible graph just to watch it fail is wasteful. Students writing LeetCode-style problems often add the degree test as a guard clause, returning an empty list or raising an exception when the criteria are not met.

How Fleury's algorithm avoids bridges

The defining trick behind Fleury's algorithm is the bridge rule. A bridge is an edge whose removal would disconnect the graph. From the current vertex, Fleury's algorithm looks at every available neighbour and refuses to cross a bridge unless there is no alternative.

Practically, this means following two steps at every iteration. First, list the unvisited edges leaving the current vertex. Second, choose among them, skipping any that would be a bridge in the remaining graph unless that neighbour leads nowhere else. The output is a sequence of vertices that, read in order, traces out an Eulerian path.

The strategy works because crossing a bridge too early strands the other side of the graph. Imagine tracing a path through the streets of Hobart's waterfront district. If you cross the only bridge to the second peninsula too soon, you may end up forced to backtrack later. Fleury's rule prevents exactly that scenario. It is the same intuition an experienced postie uses when planning a delivery walk through suburban Adelaide, preferring to "open up" the route so every street can be visited from a still-connected neighbourhood.

For disconnected candidates or graphs with no edges at all, the algorithm should return early. A common pitfall is forgetting to handle the trivial case of an empty graph, which technically satisfies every vertex having even degree but contains no path to speak of.

Code implementation in Python

Translating the rules into Python is straightforward. The standard approach keeps an adjacency list, a working copy of edges that can be safely removed, and a list recording the order of visited vertices. Below is a compact version that students often paste into a Jupyter notebook or a competitive-programming scratchpad.

from collections import defaultdict

def fleury(graph, start):
    visited = []
    g = defaultdict(dict)
    for u in graph:
        for v in graph[u]:
            g[u][v] = g[u].get(v, 0) + 1
            g[v][u] = g[v].get(u, 0) + 1

    def is_bridge(u, v):
        if g[u][v] == 1:
            return count_edges() == 1
        return False

    def count_edges():
        return sum(len(adj) for adj in g.values()) // 2

    u = start
    visited.append(u)
    while count_edges() > 0:
        for v in list(g[u]):
            if len(g[u]) > 1 and is_bridge(u, v):
                continue
            visited.append(v)
            g[u][v] -= 1
            if g[u][v] == 0:
                del g[u][v]
            g[v][u] -= 1
            if g[v][u] == 0:
                del g[v][u]
            u = v
            break
    return visited

The bridge check is the subtle part. In a multigraph, two vertices can share multiple edges, so the count is tracked separately rather than with a boolean. Readers who want a fully commented walkthrough of this snippet can contact the maintainers of the site for the companion notebook, where each line is annotated with the rule it implements.

Complexity analysis and practical limits

The naive Fleury implementation costs O(E²) time, where E is the number of edges, because each bridge check itself walks through the remaining edges. For sparse graphs with a few hundred edges, this remains comfortable. For dense networks such as a social graph in a major Australian city like Perth, the runtime grows quickly and a Hierholzer-based approach becomes preferable.

Space is more generous. The recursion-friendly version uses O(V + E) memory for the adjacency structure plus O(E) for the resulting path. Iterator-based rewrites can stream output without retaining the full trail, which matters when an Eulerian path may run through millions of edges.

Memory pressure is rarely the bottleneck. The bigger danger is implementation correctness. A bug in the bridge predicate can produce paths that miss edges or repeat them, and the output may look plausible when it is actually wrong. Pair the implementation with a verifier that compares the returned trail against the original edge list, and any discrepancy becomes obvious during testing.

Where Eulerian paths show up in real systems

Eulerian paths are not museum pieces. Postal route planners in regional Victoria still use route-building software that echoes Euler's work, picking roads such that the postie visits every block without doubling back. Inside compilers, de Bruijn sequences built from Eulerian circuits help generate test patterns for hardware. Bioinformatics pipelines stitch DNA fragments together by treating overlapping reads as edges in a graph and chasing an Eulerian path through the assembly.

Network engineers in Brisbane have described using graph-walking routines when auditing redundancy in fibre rings, where traversing each span exactly once gives a clean map of physical topology. Researchers at the Australian National University in Canberra have applied similar techniques to traffic-light phasing, ensuring that any sequence of green waves reaches every link exactly once.

Anyone curious about the broader hello ML community can visit the about page for details on how contributions are reviewed, which topics are in scope, and where future articles on graph algorithms are heading. For practising engineers and students alike, Fleury's algorithm is both a teaching tool and a working component of countless applications that touch the everyday world.

Practical recommendations for working with Fleury's algorithm