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:

The bridges of Königsberg as a graph Four vertices: the north bank N, the south bank S, the island I and the eastern land E. N and I are joined by two edges, S and I by two edges, and N, S and I are each joined to E by one edge. The degrees are N 3, S 3, I 5 and E 3, all odd. N S I E
The bridges of Königsberg as a graph

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 3,3,5,33, 3, 5, 3: 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

  1. A connected graph has degrees 2,4,4,2,62, 4, 4, 2, 6. Does it have an Euler circuit?

    Answer

    Yes

    Full solution

    Every degree is even.

  2. A connected graph has degrees 3,2,2,33, 2, 2, 3. 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.

  3. Does K6K_6 have an Euler circuit?

    Answer

    No; not even an Euler path.

    Full solution

    Every vertex has degree 55: six odd vertices.

  4. For which nn does KnK_n have an Euler circuit?

    Answer

    Odd nn (with n≥3n \ge 3)

    Full solution

    Each vertex has degree n−1n - 1, which is even exactly when nn is odd.

  5. In Königsberg, how many bridges must be added, at least, to allow an Euler path?

    Answer

    11

    Full solution

    One new bridge between two odd vertices makes them even, leaving two odd vertices, as in Example 3.

  6. Does a cycle with 55 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.

  7. 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.

  8. A student says a graph with degrees 1,1,1,11, 1, 1, 1 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.

What to learn next