Eulerian Path

Definition

An Eulerian path is a walk through a graph that visits every edge exactly once, and an Eulerian circuit is an Eulerian path that additionally starts and ends at the same vertex.

Overview

The Eulerian path problem originates from Leonhard Euler's 1736 solution to the Seven Bridges of Königsberg puzzle, widely regarded as the founding result of graph theory. Euler proved that a connected graph has an Eulerian circuit if and only if every vertex has even degree (an even number of incident edges), and has an Eulerian path (but not necessarily a circuit) if and only if exactly zero or two vertices have odd degree — if two, the path must start at one odd-degree vertex and end at the other. Existence can therefore be checked in linear time simply by counting vertex degrees and verifying graph connectivity (ignoring isolated vertices with no edges). Once existence is confirmed, an actual Eulerian path or circuit can be constructed efficiently using Hierholzer's algorithm, which builds the tour by following edges until stuck, then splicing in additional sub-circuits found by backtracking to vertices with unused edges, achieving overall O(E) time complexity. An older method, Fleury's algorithm, is more intuitive but runs slower because it must repeatedly check whether an edge is a bridge before using it, to avoid stranding remaining edges. Eulerian paths and circuits are foundational to route-planning problems where every connection, not every location, must be traversed exactly once — the defining feature that distinguishes them from Hamiltonian paths, which instead require visiting every vertex exactly once. Real-world applications include the classic Route Inspection Problem (also called the Chinese Postman Problem) for mail delivery and snow-plowing routes that must cover every street segment, DNA fragment assembly in bioinformatics using de Bruijn graphs, and circuit design and testing where every connection on a board must be verified.

Key Concepts

• Visits every edge in a graph exactly once
• An Eulerian circuit additionally returns to its starting vertex
• Exists in a connected graph iff all vertices have even degree (circuit) or exactly two have odd degree (path)
• Existence checkable in linear time via degree counting
• Constructed efficiently via Hierholzer's algorithm in O(E) time
• Distinct from Hamiltonian paths, which visit every vertex rather than edge
• Originates from Euler's 1736 Seven Bridges of Königsberg proof
• Underlies the Route Inspection (Chinese Postman) Problem

Use Cases

Frequently Asked Questions

Related in Computer Science