Eulerian Path
1. Definition & Notation
In graph theory, an Eulerian path is a trail in a finite graph that visits every edge exactly once. If the path starts and ends at the same vertex, it is called an Eulerian circuit (or Eulerian tour).
Formally, let \(G = (V, E)\) be an undirected graph. A sequence of vertices and edges \(v_0, e_1, v_1, e_2, ..., e_k, v_k\) is an Eulerian path if:
For directed graphs, the definition adapts naturally: an Eulerian path traverses every arc exactly once, respecting edge direction.
1.1 Historical Context
The concept originates from Euler's seminal 1736 paper "Solutio problematis ad geometriam situs pertinentis" (Solution of a problem relating to the geometry of position). Euler modeled the city of Königsberg's seven bridges and four landmasses as a graph, proving that no walk could cross each bridge exactly once. This work is widely regarded as the birth of graph theory and topology.
2. Existence Conditions
Euler's theorem provides necessary and sufficient conditions for the existence of Eulerian paths and circuits in connected graphs (ignoring isolated vertices):
Euler's Theorem (Undirected Graphs)
A connected graph \(G\) has an Eulerian circuit if and only if every vertex has an even degree. It has an Eulerian path (but not a circuit) if and only if exactly two vertices have an odd degree. All other vertices must have even degree.
For directed graphs, a connected underlying graph admits an Eulerian circuit iff every vertex has equal in-degree and out-degree. An Eulerian path exists iff exactly one vertex has out-degree = in-degree + 1 (start node), exactly one has in-degree = out-degree + 1 (end node), and all others are balanced.
3. Algorithms & Construction
While existence can be checked in \(O(V)\) time by counting vertex degrees, constructing an actual Eulerian path requires a traversal algorithm. The most efficient and widely taught method is Hierholzer's Algorithm (1873).
1. Verify Eulerian path/circuit conditions.
2. Start at a vertex with odd degree (or any vertex if circuit).
3. Traverse edges arbitrarily until returning to the start vertex, forming a cycle \(C\).
4. While there exists a vertex \(v\) in \(C\) with unused incident edges:
a. Start a new tour at \(v\), tracing unused edges until returning to \(v\).
b. Splice this new cycle into \(C\) at \(v\).
5. Return the merged cycle as the Eulerian path/circuit.
Time Complexity: \(O(E)\) — each edge is visited exactly once. Space Complexity: \(O(V + E)\) for adjacency lists and recursion/stack storage.
4. Applications
Eulerian paths and circuits have profound practical applications across multiple disciplines:
- Network Routing: Optimizing delivery routes, postal mail collection, and street-sweeping schedules (Chinese Postman Problem extensions).
- DNA Sequencing: De Bruijn graphs in genomics use Eulerian paths to assemble short DNA fragments into complete sequences efficiently.
- Circuit Design: Verifying and constructing closed-loop electronic circuits and PCB trace routing.
- Robotics & Automation: Path planning for vacuum robots and inspection drones to cover all necessary pathways without repetition.
Did You Know?
The "Chinese Postman Problem" (1962) generalizes Eulerian paths to graphs that may not satisfy Euler's conditions, finding the shortest closed route that traverses every edge at least once by optimally duplicating edges.