Eulerian Trails and Circuits: Explained with Examples

An Eulerian trail is a walk that uses every edge of a graph exactly once. An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex — a round trip covering every edge once. The idea comes from Leonhard Euler's 1736 solution to the bridges of Königsberg: can you walk through the city crossing each of its seven bridges exactly once?

Eulerian trails matter because they solve "cover everything without repeating" problems: a street sweeper that must clean every street once, a postman covering every road, or drawing a figure without lifting the pen or retracing a line.

Key Concepts

• Eulerian trail: a trail (no repeated edges) covering every edge of the graph exactly once.
• Eulerian circuit: an Eulerian trail that returns to its starting vertex.
• Euler's theorem: a connected graph has an Eulerian circuit iff every vertex has even degree; it has an Eulerian trail (but no circuit) iff it has exactly 0 or 2 odd-degree vertices.
• Königsberg: the original puzzle had four land areas with 3, 3, 3 and 5 bridges — four odd vertices — so no Eulerian trail exists.
• Fleury's algorithm: a method to find an Eulerian trail: keep walking, never crossing a bridge unless forced.

How It Works

Euler's insight was about entering and leaving. Each time a trail passes through a middle vertex, it uses one edge to arrive and a different edge to leave — a pair of edges. So every middle vertex must have even degree. In a closed circuit the start vertex also gets paired arrivals and departures, so all vertices are even. In an open trail, the start and end vertices each have one unpaired edge — exactly two odd-degree vertices. Counting odd degrees decides everything: 0 means a circuit exists, 2 means only an open trail exists, anything else means impossible.

Worked Example

Take a house-shaped graph: square base A–B–C–D–A plus roof A–E–C. Degrees: deg(A) = 3, deg(B) = 2, deg(C) = 3, deg(D) = 2, deg(E) = 2. Sum = 12 = 2 × 6 — consistent. Odd-degree vertices: A and C — exactly 2. By Euler's theorem an Eulerian trail exists but no circuit. One such trail: A–B–C–D–A–E–C, using all six edges exactly once, starting at A and ending at C — the two odd vertices. Trying to return to the start would force reusing an edge, which the theorem says is impossible.

Common Misconceptions

• Vertices may repeat — edges may not. An Eulerian trail is a trail, not a path: revisiting a vertex is fine and often necessary. Only edge reuse is forbidden.
• Exactly 2 odd vertices gives a trail, not a circuit. With two odd vertices the trail must start at one and end at the other. A circuit needs all vertices even.
• The graph must be connected (ignoring isolated vertices). A disconnected graph can satisfy the degree rule in each piece yet still have no single trail covering all edges.

Real-World Applications

• Street sweeping and snow ploughing: routes that cover every street once with minimum retracing are Eulerian trail problems.
• Postal delivery: the Chinese postman problem extends this to graphs where retracing is unavoidable.
• Pen puzzles: "draw without lifting the pen" is possible exactly when the figure has 0 or 2 odd-degree junctions.
• DNA fragment assembly: arranging genome fragments uses Eulerian trails through overlap graphs.

Euler turned a city walk into a counting rule: all even degrees give a circuit, exactly two odd degrees give a trail. Count the odd degrees first — that single number tells you whether the journey is possible.