Euler Path
An Euler path (or Eulerian path) is a trail in a graph that visits every edge exactly once, without necessarily returning to the starting vertex. An Euler circuit (or Eulerian circuit) is an Euler path that begins and ends at the same vertex. A connected graph has an Euler path if and only if it has exactly zero or two vertices of odd degree; if two odd-degree vertices exist, the path must start and end at those vertices.
Worked Example
Problem
The Königsberg bridge problem: a city has 4 landmasses (A, B, C, D) connected by 7 bridges. A–B: 2 bridges, A–C: 2 bridges, A–D: 1 bridge, B–D: 1 bridge, C–D: 1 bridge. Does an Euler path exist?
Solution
Step 1: Model as a multigraph: vertices = {A, B, C, D}, edges = the 7 bridges. Step 2: Calculate degrees: deg(A) = 2 + 2 + 1 = 5 (odd) deg(B) = 2 + 1 = 3 (odd) deg(C) = 2 + 1 = 3 (odd) deg(D) = 1 + 1 + 1 = 3 (odd) Step 3: Count odd-degree vertices = 4. Step 4: Euler path condition: exactly 0 or 2 vertices with odd degree. Step 5: 4 odd-degree vertices → condition fails.
Answer
No Euler path exists. All 4 vertices have odd degree; an Euler path requires exactly 0 or 2 odd-degree vertices.
Conditions for Euler Paths and Circuits
| Graph Type | Odd-Degree Vertices | Euler Path? | Euler Circuit? | Start/End |
|---|---|---|---|---|
| Undirected connected | 0 odd-degree vertices | Yes | Yes | Any vertex |
| Undirected connected | 2 odd-degree vertices | Yes | No | Must start/end at odd-degree vertices |
| Undirected connected | 4+ odd-degree vertices | No | No | Not possible |
| Directed connected | All in-deg = out-deg | Yes (circuit) | Yes | Any vertex |
| Directed connected | One vertex out − in = 1, one in − out = 1 | Yes (path) | No | Out-excess to in-excess |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Hamiltonian Cycle
A Hamiltonian cycle (or Hamiltonian circuit) is a closed path in a graph that visits every vertex exactly once before returning to the starting vertex. Unlike the Euler path (which covers every edge), the Hamiltonian cycle covers every vertex. Determining whether a Hamiltonian cycle exists in an arbitrary graph is an NP-complete problem, making it one of the central challenges in computational complexity and combinatorial optimisation (e.g., the Travelling Salesman Problem).
Graph Path
A path in a graph is a sequence of vertices in which each consecutive pair is connected by an edge and no vertex is repeated. The length of a path is defined as the number of edges it traverses. Paths are central to graph algorithms such as Dijkstra's shortest-path algorithm, breadth-first search, and depth-first search, which are used in navigation systems, network routing, and AI planning.
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
The Euler path is named after Swiss mathematician Leonhard Euler (1707–1783), who published the solution to the Königsberg bridge problem in 1736 — the paper considered the birth of graph theory. "Euler" is pronounced "OY-ler." The problem asked whether one could walk through the city crossing each bridge exactly once.