Discrete Math · Undergraduate
Euler and Hamilton Paths: The Bridges of Königsberg
Quick answer
An Euler path uses every edge of a graph exactly once; an Euler circuit does so and returns to its start. Euler's theorem decides the question by counting odd-degree vertices: a connected graph has an Euler circuit when every degree is even, and an Euler path when exactly two degrees are odd, starting at one odd vertex and ending at the other. That settled the bridges of Königsberg, whose four land masses all had odd degree. Hamilton paths, which visit every vertex once, have no simple test.
What you'll learn
- Define Euler paths and circuits
- Use degrees to decide whether they exist
- Find an Euler path when one exists
- Distinguish Euler paths from Hamilton paths
Seven bridges
The city of Königsberg sat on both banks of a river and on an island, joined by seven bridges. Its citizens asked whether anyone could walk through the city crossing every bridge exactly once. In 1736 Euler answered no, and in doing so started graph theory.
Make each land mass a vertex and each bridge an edge:
A walk using every edge exactly once is an Euler path. If it returns to its starting point, it is an Euler circuit.
Why odd degrees decide it
Follow an Euler path. Each time it passes through a vertex, it enters on one edge and leaves on another, using up two of that vertex’s edges. So at every vertex other than the start and the end, the edges come in pairs and the degree must be even. Only the two ends of the path can have odd degree, because there the path leaves without entering, or enters without leaving.
Euler’s theorem. A connected graph has an Euler circuit exactly when every vertex has even degree, and an Euler path exactly when zero or two vertices have odd degree.
In Königsberg the degrees are : four odd vertices, two too many. No such walk exists.
Worked examples
Hamilton paths
A Hamilton path visits every vertex exactly once, and a Hamilton cycle returns to its start. The square with a diagonal has the Hamilton cycle A–B–C–D–A. The two questions sound alike, but they behave very differently: Euler’s question has the simple degree test above, while no simple test is known for Hamilton paths. Finding the shortest Hamilton cycle, the traveling salesperson problem, is one of the most studied hard problems in computing.
Common mistakes
Practice problems
-
A connected graph has degrees . Does it have an Euler circuit?
Answer
Yes
Full solution
Every degree is even.
-
A connected graph has degrees . Does it have an Euler circuit? An Euler path?
Answer
No circuit; yes, a path
Full solution
Exactly two odd vertices: a path from one to the other, but no circuit.
-
Does have an Euler circuit?
Answer
No; not even an Euler path.
Full solution
Every vertex has degree : six odd vertices.
-
For which does have an Euler circuit?
Answer
Odd (with )
Full solution
Each vertex has degree , which is even exactly when is odd.
-
In Königsberg, how many bridges must be added, at least, to allow an Euler path?
Answer
Full solution
One new bridge between two odd vertices makes them even, leaving two odd vertices, as in Example 3.
-
Does a cycle with vertices have a Hamilton cycle? An Euler circuit?
Answer
Both
Full solution
Going around the cycle visits every vertex once and uses every edge once.
-
Find an Euler circuit in the graph with edges A–B, B–C, C–A, C–D, D–E, E–C.
Answer
A–B–C–D–E–C–A
Full solution
Degrees: A 2, B 2, C 4, D 2, E 2, all even. The circuit runs around one triangle, then the other, meeting at C.
-
A student says a graph with degrees has an Euler path because its degree sum is even. What went wrong?
Answer
It has four odd vertices; an Euler path allows at most two.
Full solution
An even degree sum only says the graph can exist. Such a graph is two separate edges, and no single walk covers both.
Frequently asked questions
What is an Euler path?
A route through a graph that uses every edge exactly once. If it also ends where it started, it is an Euler circuit.
When does a graph have an Euler circuit?
When it is connected and every vertex has even degree.
When does a graph have an Euler path but no circuit?
When it is connected and exactly two vertices have odd degree. The path must start at one of them and end at the other.
Why were the bridges of Königsberg impossible?
The four land masses had degrees 3, 3, 3 and 5, all odd. A path can have at most two odd-degree vertices, its two ends.
What is a Hamilton path?
A path that visits every vertex exactly once. Unlike Euler paths, no simple rule decides whether one exists; it is a famously hard problem.