Eulerian Circuits and Trails: The Seven Bridges Problem

Introduction

Imagine you are driving a snowplow for your city. Your job is to drive down every single street in the neighbourhood to clear the snow. But you want to be perfectly efficient:

• You must plow every street exactly once
• You must not waste fuel driving a street you’ve already cleared
• You need to end your shift back at the garage where you started

Can you do it? Whether or not you can depends entirely on the degrees of the intersections — a beautifully simple test discovered in 1736 by Leonhard Euler.

If you can complete this loop, you have just completed an Eulerian Circuit.

What Is an Eulerian Circuit?

Definition

An Eulerian circuit (also called an Eulerian tour or Eulerian cycle) is a closed walk that traverses every edge of the graph exactly once.

Breaking down the definition:
- Closed walk: starts and ends at the same vertex
- Every edge: no edge is left unvisited
- Exactly once: no edge is repeated
- Vertices may be visited more than once — only edges have the “once” restriction

A connected graph that possesses an Eulerian circuit is called an Eulerian graph.

Relationship to Earlier Concepts

From the walk hierarchy (Post 09):
- An Eulerian circuit is a circuit (closed walk, no repeated edges) that additionally uses all edges
- It is the most demanding closed walk possible

The Seven Bridges of Königsberg

Historical Background

In 1736, Swiss mathematician Leonhard Euler (pronounced “Oiler”) was presented with a puzzle from the city of Königsberg, Prussia (now Kaliningrad, Russia).

The city sat on the Pregel River, which created two islands. Seven bridges connected the four landmasses. The townspeople’s puzzle: can you walk through the city crossing every bridge exactly once and return to your starting point?

Translating the City to a Graph

Euler’s genius was to abstract away all the irrelevant geography and keep only what matters:

The four vertices are:
- N — North bank (3 bridges: to W, E, E)
- S — South bank (3 bridges: to W, E, E)
- W — West island (3 bridges: to N, S, E)
- E — East island (5 bridges: to N, N, S, S, W)

Euler’s Proof of Impossibility

Count the degree of every vertex:

All four vertices have odd degree. As we will prove below, an Eulerian circuit requires every vertex to have even degree. Having four odd-degree vertices makes the circuit — and in fact even any Eulerian trail — impossible. The puzzle has no solution.

This proof founded graph theory as a mathematical discipline.

Euler’s Theorem — The Even Degree Test

Intuition

Think about what happens each time the snowplow passes through an intersection (vertex):

• It arrives via one street → +1 edge
• It departs via another street → +1 edge

Each visit to a non-terminal vertex consumes a pair of edges. The total edges at that vertex from all visits must therefore be even.

The only vertex that can have an odd number of edges is the very start/end vertex — but in a circuit, start = end, so it also gets an entry and exit at the very end, keeping it even.

The Theorem

Euler’s Theorem: A connected graph $G$ has an Eulerian circuit if and only if every vertex has even degree.

$$G \text{ is Eulerian} \iff \deg(v) \equiv 0 \pmod{2} \quad \forall\, v \in V$$

“If and only if” means both directions hold:
- If all degrees are even → an Eulerian circuit exists
- If an Eulerian circuit exists → all degrees must be even

Testing Graphs for Eulerian Circuits

Scenario A — Square with Both Diagonals (Not Eulerian)

A square A–B–C–D with both diagonals A–C and B–D added. Check every vertex:

All four vertices are odd — no Eulerian circuit exists. In fact, with four odd-degree vertices, not even an Eulerian trail is possible (that would need exactly two odd vertices).

Scenario B — The House Shape (Eulerian)

A graph built from a square base (A–B–C–D) with additional diagonals and a roof peak E, arranged so every vertex degree is even:

Every vertex is even → this is an Eulerian graph. You can trace every edge exactly once and return to your starting point. Because any vertex can be the starting point of an Eulerian circuit, you may begin anywhere.

A Full Eulerian Circuit

This graph has all even degrees (green vertices = degree 4, blue = degree 2). The orange edges show one valid Eulerian circuit. Every edge is covered exactly once and the walk returns to the start.

Eulerian Trails (Open Eulerian Walks)

Definition

What if the snowplow driver does not need to return to the garage? They just want to clear every street once and finish wherever they end up.

An Eulerian trail (also called an Eulerian path or Eulerian walk) is an open walk that traverses every edge of the graph exactly once. It starts and ends at different vertices.

• Still visits every edge exactly once ✓
• Does not need to return to the start ✗ (open walk)

The Trail Theorem

What degree condition allows an Eulerian trail?

Thought experiment: Start with a graph that has an Eulerian circuit (all even degrees). Erase the very last edge you drew.

• The walk is no longer closed — it becomes open
• The two terminal vertices (start and end) each lost one edge from their degree: even − 1 = odd
• All middle vertices are untouched — still even

This gives the trail condition:

Trail Theorem: A connected graph has an Eulerian trail if and only if it has exactly two vertices of odd degree. The trail must start at one odd-degree vertex and end at the other.

Note: the Handshaking Lemma guarantees the number of odd-degree vertices is always even, so counts of 1, 3, 5, … never occur.

Eulerian Trail Example

This graph has exactly two odd-degree vertices: A (deg 3, orange) and E (deg 3, orange). All other vertices are even. By the Trail Theorem:

• An Eulerian trail exists
• It must start at A and end at E (or vice versa)
• An Eulerian circuit does not exist (the two odd vertices prevent closing the loop)

One valid trail: A → B → C → E → C → D → A → C — wait, we need to be careful. A valid Eulerian trail starting from A visits every edge exactly once and finishes at E.

Finding an Eulerian Circuit: Hierholzer’s Algorithm

Knowing a circuit exists is great — but how do you actually find one efficiently?

Hierholzer’s Algorithm (1873) does it in $O(|E|)$ time.

The Algorithm

1. Start at any vertex $v$. Follow edges (removing each as you use it) until you return to $v$. This gives a sub-circuit.
2. If unused edges remain, find a vertex $u$ on your current circuit that still has unused edges.
3. From $u$, follow unused edges until you return to $u$ — another sub-circuit.
4. Splice this new sub-circuit into the existing one at $u$.
5. Repeat from step 2 until all edges are used.

Demonstration

The two-colour graph has two cycles sharing vertex C (orange):
- Purple cycle: A → B → C → A (triangle)
- Orange cycle: C → D → E → F → C (square)

Step 1: Start at A. Follow purple edges: A → B → C → A. Sub-circuit found.

Step 2: Check unused edges from vertices on the sub-circuit. Vertex C has unused orange edges.

Step 3: From C, follow orange edges: C → D → E → F → C. Second sub-circuit found.

Step 4: Splice at C: the full circuit becomes A → B → C → D → E → F → C → A.

Every edge covered exactly once. ✓

Eulerian vs. Hamiltonian — Don’t Mix Them Up

A common confusion for students is between Eulerian and Hamiltonian problems.

Eulerian is the “easy” version — a clean degree test settles everything in linear time. Hamiltonian is one of the hardest problems in computer science.

Practice Problems

Problem 1: Does an Eulerian Circuit Exist?

Question: Graph $G$ has 5 vertices with degrees $[2, 4, 2, 4, 4]$. Does an Eulerian circuit exist?

Problem 2: Circuit or Trail?

Question: A connected graph has exactly two vertices of odd degree. What type of Eulerian walk exists, if any?

Problem 3: Königsberg Revisited

Question: How many bridges would you need to add to the Königsberg graph to make an Eulerian circuit possible? Where would you add them?

Problem 4: Degree Arithmetic

Question: A connected graph has 6 vertices and 9 edges. The degree sequence is $[3, 3, 4, 4, 2, 2]$. Does an Eulerian circuit or trail exist?

Problem 5: Chinese Postman Setup

Question: A postman’s route graph has all even-degree vertices except vertices X (deg 5) and Y (deg 3). What is the minimum number of edges that must be repeated to deliver all mail and return to the start?

Summary Table

Key theorem pairs:
- Eulerian Circuit: connected + all degrees even ↔ circuit exists
- Eulerian Trail: connected + exactly 2 odd degrees ↔ trail exists (start and end at odd vertices)

Real-World Applications

Mail Carriers and Garbage Trucks

Every street must be serviced once. This is the Chinese Postman Problem (also called the Route Inspection Problem): find the minimum-weight closed walk that covers every edge. If the graph is already Eulerian, the answer is just the Eulerian circuit. If not, the solution involves finding a minimum-weight matching of the odd-degree vertices and duplicating those paths.

DNA Fragment Assembly

Shotgun sequencing produces millions of short DNA reads. Bioinformaticians model these as edges in a de Bruijn graph where vertices are $k$-mers (substrings of length $k$) and edges represent reads. Assembling the full genome reduces to finding an Eulerian path through this graph — a direct application of the Trail Theorem.

Network Testing and Inspection

Any system where every connection must be checked — optical fibre networks, road inspection drones, PCB trace testing — reduces to finding an Eulerian walk on the network graph to minimise total distance travelled.

Puzzle Design

The classic “draw this figure without lifting your pen” puzzle asks exactly whether an Eulerian circuit (if the figure is closed) or Eulerian trail (if open) exists. The degree test answers instantly.

Key Takeaways

1. An Eulerian circuit is a closed walk visiting every edge exactly once; it returns to its starting vertex.
2. A graph is Eulerian (has an Eulerian circuit) iff it is connected and every vertex has even degree.
3. An Eulerian trail is an open walk visiting every edge exactly once; it starts and ends at different vertices.
4. An Eulerian trail exists iff the graph is connected and exactly two vertices have odd degree; those two vertices are the mandatory start and end.
5. The number of odd-degree vertices is always even (Handshaking Lemma) — counts of 1, 3, 5, … cannot occur.
6. Hierholzer’s algorithm finds an Eulerian circuit in $O(|E|)$ time by splicing sub-circuits together.
7. Eulerian (edge-visit) and Hamiltonian (vertex-visit) problems are fundamentally different: one has a linear-time test; the other is NP-complete.
8. Euler’s 1736 proof that the Königsberg bridges had no solution is the birth certificate of graph theory.

Explore Further

Use the GraphArena Playground to experiment:
- Build the Königsberg graph and verify all four vertices have odd degree
- Build the house-shape graph and trace an Eulerian circuit by hand
- Add one edge to the square-with-diagonals to create a graph with exactly two odd vertices — find the Eulerian trail
- Implement Hierholzer’s algorithm on the two-cycle graph: start with the triangle sub-circuit, then splice in the square
- Try building a graph with 4 odd-degree vertices and confirm no Eulerian walk is possible

The degree test for Eulerian circuits is one of the most satisfying results in all of mathematics: a single numerical condition on each vertex completely determines whether an exponentially large search space contains a solution.