Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 68 ยท Graph Theory

Euler and Hamilton Paths

Learn when a graph has an Euler circuit or a Hamilton cycle, from the Konigsberg bridges to Hierholzer's algorithm and brute-force search.

In 1736 the people of Konigsberg wondered whether a walk existed that crossed each of the town's seven bridges exactly once. Leonhard Euler showed that no such walk exists, and in doing so he founded graph theory. His argument is a gem: instead of trying routes, he looked only at the degrees of the land masses.

This lesson compares two superficially similar questions. An Euler walk uses every edge exactly once; the question has a clean answer and a fast algorithm. A Hamilton cycle visits every vertex exactly once; the question looks almost the same but is among the hardest problems in computer science. We build a checker, a constructive algorithm for the first, and a brute-force search for the second.

Two kinds of grand tour

Euler Use every edge exactly once.
Hamilton Visit every vertex exactly once.
1 / 2

The Konigsberg bridges

Model each land mass as a vertex and each bridge as an edge. Two bridges can join the same pair of land masses, so this is a multigraph.

graph LR
  N["North bank"] --- I["Island"]
  N --- I
  S["South bank"] --- I
  S --- I
  I --- E["East part"]
  N --- E
  S --- E

Seven bridges, four land masses. The island has degree 5 and each other land mass has degree 3.

Whenever a walk passes through a vertex, it uses one edge to enter and another to leave, so edges at that vertex are consumed in pairs. A vertex can be odd only if the walk starts or ends there. Since all four land masses have odd degree, and a walk has just two ends, the walk cannot exist.

Euler's criteria

An Euler trail uses every edge exactly once; an Euler circuit is an Euler trail that ends where it began. For a graph in which all edges lie in one connected piece (ignore isolated vertices):

  • It has an Euler circuit exactly when every vertex has even degree.
  • It has an Euler trail that is not a circuit exactly when exactly two vertices have odd degree; the trail must start at one and end at the other.
  • With any other number of odd vertices, no Euler trail exists. (The handshake lemma already forbids exactly one odd vertex.)

This is a rare case where a global property of the graph is settled by a local count.

Python Classify graphs by Euler's criteria

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The "house" is the classic pencil puzzle: draw it without lifting your pencil. Two corners have odd degree, so you must start at one of them.

Hierholzer's algorithm

Knowing that a circuit exists is not the same as finding one. Hierholzer's algorithm builds it in time proportional to the number of edges:

  1. Start at any vertex and follow unused edges, always moving on, until you are stuck. For a graph with all even degrees you can only get stuck at the start vertex.
  2. If some vertex on this closed walk still has unused edges, start a new closed walk from it and splice that loop into the first walk.
  3. Repeat until every edge is used.

The usual implementation uses a stack. Push the start vertex; while the stack is not empty, look at the top vertex. If it has an unused edge, follow it and push the neighbor. If not, pop it and prepend it to the answer. The popped vertices, read in reverse pop order, form the circuit. Give every edge an id so that parallel edges work and an edge is never used twice.

Python Hierholzer's algorithm builds an Euler circuit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For a graph with exactly two odd vertices, starting at one of them makes the same code produce an Euler trail ending at the other. If you start at an even vertex, the walk may get stuck early and the result will not use every edge, which is why the starting rule matters.

Hamilton cycles

A Hamilton path visits every vertex exactly once; a Hamilton cycle also returns to the start through an edge. Edges may be left unused. The traveling salesman problem asks for the cheapest Hamilton cycle in a weighted graph.

Despite the similar wording, there is no degree count that decides this. Some partial clues exist:

  • Dirac's theorem: a simple graph with n โ‰ฅ 3 vertices where every vertex has degree at least n/2 has a Hamilton cycle. It is sufficient, not necessary: a plain cycle C_n has Hamilton cycles with degrees 2 only.
  • A vertex of degree 1 rules out a Hamilton cycle, since a cycle needs two edges at every vertex.
  • A bipartite graph with sides of different sizes has no Hamilton cycle, because a cycle alternates between the sides. This explains why K_{2,3} has none.

In general, finding out requires search. The brute-force method tries paths by backtracking: extend a partial path by an unvisited neighbor, and undo the choice when stuck.

Python Brute-force search for Hamilton cycles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cube (vertices are the 3-bit strings, edges join strings differing in one bit) has 6 Hamilton cycles; the first one found is a Gray code, in which consecutive codes differ in a single bit. K(2,3) has none. The complete graphs show the explosive growth: K_n has (n-1)!/2 Hamilton cycles, which gives 3, 12, 60 and 360 for n = 4 to 7. At n = 20 the count exceeds 10^16, so naive enumeration is hopeless.

Why Hamilton is hard

Deciding whether a graph has a Hamilton cycle is NP-complete: a proposed cycle is quick to check (just verify the list), but no known algorithm finds one in time polynomial in n for all graphs, and most experts believe none exists. Clever dynamic programming over subsets reduces the cost from about n! to about 2^n ยท nยฒ, enough for roughly 20 to 25 vertices; practical solvers use heuristics beyond that.

Contrast this with Euler: the same question about edges needs only a degree count and one linear pass. That gap between "easy to state, easy to solve" and "easy to state, very hard to solve" is a recurring theme in computer science (see Algorithms, Recursion and Growth).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A connected graph has exactly 4 vertices of odd degree. What can you conclude?

    An Euler trail allows at most two odd-degree vertices (its two ends). Four odd vertices rule it out.
  2. 2. Which connected graph has an Euler circuit?

    C_6 has all degrees equal to 2. K_4 has all degrees 3 (odd). The path and the star have vertices of degree 1.
  3. 3. What is the key difference between Euler and Hamilton problems?

    Euler walks cover edges and are decided by counting odd degrees. Hamilton cycles cover vertices and have no known efficient test.
  4. 4. Why can K(2,3), the complete bipartite graph with sides of size 2 and 3, not have a Hamilton cycle?

    Every edge goes between the sides, so a cycle alternates and visits equally many vertices from each side. 2 is not 3.
  5. 5. How many Hamilton cycles does K_6 have, ignoring direction and starting point?

    (n-1)!/2 = 5!/2 = 60.

Summary

  • An Euler circuit uses every edge once: it exists in a connected graph exactly when all degrees are even. An Euler trail needs exactly 0 or 2 odd-degree vertices.
  • Euler's argument about the Konigsberg bridges shows the walk is impossible because four land masses have odd degree.
  • Hierholzer's algorithm builds an Euler circuit in linear time by splicing closed loops together.
  • A Hamilton cycle visits every vertex once. Dirac's theorem and bipartite-balance arguments give clues, but deciding existence is NP-complete.
  • Brute-force search explodes ((n-1)!/2 cycles in K_n); subset dynamic programming pushes the limit to a few dozen vertices.

Next: Trees and Spanning Trees, the sparsest connected graphs.