Eulerian Paths and Circuits

1. What Is an Eulerian Trail?

An Eulerian trail (also called an Euler path) is a route through a graph that uses every edge exactly once. You may pass through the same vertex many times, but you are never allowed to travel along the same edge twice.

It answers a surprisingly practical question: given a network of roads, pipes, or cables, can I traverse all of them without ever repeating a connection?

2. Euler Trail vs Euler Circuit

The two terms are closely related but not identical:

• An Eulerian trail uses every edge once and may start and end at different vertices.
• An Eulerian circuit (or Euler cycle) is a closed Eulerian trail — it uses every edge once and returns to its starting vertex.

Every Eulerian circuit is also an Eulerian trail, but the reverse is not true. Which one a graph supports depends entirely on the degrees of its vertices.

3. The Seven Bridges of Königsberg

The Prussian city of Königsberg was split by a river into four landmasses, joined by seven bridges. Citizens wondered whether they could take a walk that crossed every bridge exactly once and returned to the start.

In 1736, Leonhard Euler proved that no such walk exists. He modeled each landmass as a vertex and each bridge as an edge, then observed something decisive: every time you enter a landmass over one bridge, you must leave it over another, so every "pass-through" vertex needs an even number of bridges. All four of Königsberg's vertices had an odd number of bridges, making the walk impossible. This proof is widely regarded as the birth of graph theory. (See our history of graph theory.)

4. The Degree Rule: When Does One Exist?

The degree of a vertex is the number of edges touching it. Euler's insight gives simple, exact rules for a connected graph:

• An Eulerian circuit exists if and only if every vertex has even degree.
• An open Eulerian trail exists if and only if exactly two vertices have odd degree — and the trail must start at one and end at the other.
• If more than two vertices have odd degree, no Eulerian trail exists.

The graph must also be connected. Otherwise, just count the odd-degree vertices and you have your answer.

5. Finding One: Fleury's and Hierholzer's Algorithms

Once you know a trail exists, two classic algorithms construct it:

Fleury's Algorithm

Walk the graph one edge at a time, and never cross a bridge (an edge whose removal would disconnect the graph) unless you have no other choice. It is easy to understand, but constantly checking for bridges makes it relatively slow.

Hierholzer's Algorithm

The efficient choice, running in O(E) time. Follow edges to form a closed loop, then repeatedly find a vertex on your current path that still has unused edges and splice in another loop there. When no unused edges remain, the loops merge into a single Eulerian circuit.

6. Euler vs Hamiltonian Paths

These two are constantly confused, but they are completely different problems:

• An Eulerian path visits every edge once.
• A Hamiltonian path visits every vertex once.

The twist is computational: deciding whether an Eulerian trail exists is easy (just count odd degrees), while deciding whether a Hamiltonian path exists is NP-complete — among the hardest problems in computer science. The Traveling Salesperson Problem is a famous Hamiltonian-style challenge.

7. Real-World Applications

• Route inspection (Chinese Postman Problem): finding the shortest route that covers every street — mail delivery, garbage collection, snow plowing, street sweeping.
• DNA sequencing: modern genome assembly builds a de Bruijn graph from short reads and finds an Eulerian path to reconstruct the sequence.
• Network maintenance: inspecting or testing every link in a telecom or utility network exactly once.
• "One-stroke" drawings: the classic puzzle of drawing a figure without lifting your pen is exactly an Eulerian-trail question.