Skip to content
Tutorials Center
My learning

Topics

Lesson 147 of 225 ยท Shortest Paths and Spanning Trees

Eulerian and Hamiltonian Paths

Learn Euler paths and circuits with the degree test and Hierholzer's algorithm, then see why Hamiltonian paths are hard, with backtracking and a TSP bitmask preview.

In 1736 the people of Konigsberg wondered whether they could take a walk that crossed each of the city's seven bridges exactly once. Leonhard Euler showed it was impossible, and in doing so invented graph theory. His idea: forget the map, keep only the land masses (vertices) and the bridges (edges). The question becomes whether a graph has a walk that uses every edge exactly once.

There is a sister question that sounds almost identical: is there a walk that visits every vertex exactly once? Surprisingly, the first question is easy (a quick degree check and a linear-time algorithm) while the second is one of the famous hard problems of computer science. This lesson explains both, implements Hierholzer's algorithm for Euler paths, and previews the travelling salesperson problem (TSP) as the practical face of Hamiltonian paths. You should know graph representations and DFS first.

Definitions

Term Visits Closed?
Eulerian path every edge exactly once no, may end elsewhere
Eulerian circuit every edge exactly once yes, ends where it started
Hamiltonian path every vertex exactly once no
Hamiltonian cycle every vertex exactly once yes

Vertices may repeat in an Eulerian walk (you pass through a junction several times); edges may not. In a Hamiltonian path, vertices may not repeat, and many edges are simply never used.

When does an Euler path exist?

Think about a vertex in the middle of a walk. Each time you pass through, you use one edge to enter and another to leave, so edges at that vertex are used in pairs. That means every vertex the walk passes through must have even degree, with exceptions only for the start and end of the walk (which use one unpaired edge each).

For an undirected graph whose edges all lie in one connected piece:

  • Eulerian circuit: every vertex has even degree.
  • Eulerian path (not a circuit): exactly two vertices have odd degree. The path must start at one and end at the other.
  • Otherwise: no Eulerian path.
TEXT
Konigsberg: 4 land masses (A, B, C, D), 7 bridges

  A-B twice, A-C twice, A-D, B-D, C-D

  degrees: A = 5, B = 3, C = 3, D = 3
  four odd vertices -> no Euler path

Four vertices with odd degree, so Euler's walk is impossible. For a directed graph the rule is about in and out degrees instead:

  • Circuit: every vertex has in-degree equal to out-degree.
  • Path: one vertex has out - in = 1 (the start), one has in - out = 1 (the end), all others balanced.

In both cases you also need all edges to be in one connected component (isolated vertices without edges do not matter).

Python Checking the Euler conditions

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.

Hierholzer's algorithm

Knowing a path exists is half the job; we also want to produce it. A naive "keep walking, never reuse an edge" can get stuck: you may use up an edge you needed to come back for. Hierholzer's algorithm (1873) avoids that and runs in O(V + E).

The idea: walk along unused edges until you get stuck. In a graph where all degrees are even, you can only get stuck at the start vertex, so you have traced a closed loop. If some vertex on the loop still has unused edges, start a new loop from there and splice it into the first one. Repeat until every edge is used.

The usual iterative version does the splicing with a stack:

  1. Push the start vertex on a stack.
  2. Look at the top vertex u. If it has an unused edge u -> v, remove that edge and push v.
  3. If u has no unused edges, pop it and append it to the answer.
  4. When the stack is empty, reverse the answer. That is the Euler path.
TEXT
graph: triangle 1-2-3 with a tail 3-4, start at 3 (an odd vertex)

stack [3]            take edge 3-4          -> [3, 4]
stack [3, 4]         4 is stuck: pop        answer [4]
stack [3]            take 3-1, 1-2, 2-3     -> [3, 1, 2, 3]
stack [3, 1, 2, 3]   3 is stuck: pop all    answer [4, 3, 2, 1, 3]

reverse the answer:  3 1 2 3 4

The walk first took the dead-end edge 3-4. A vertex is only written down when it is completely finished, so the dead end lands at the far end of the answer and the loop through the triangle is spliced in front of it. That is the whole trick behind the "splicing" described above.

Python Hierholzer's algorithm (undirected)

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.

Two details are worth noticing. First, we store each edge with an id so that using it from one end removes it from the other end too; with multigraphs, comparing endpoints alone would not be enough. Second, the final length check (len(edges) + 1 vertices) catches the case where the degrees were fine but the edges live in several components.

Directed graphs: reconstructing an itinerary

A classic use of Euler paths is rebuilding a trip from a pile of tickets. Each ticket (from, to) is a directed edge; the trip uses every ticket exactly once. In a directed graph Hierholzer is even simpler, since each edge has just one end. If you want the lexicographically smallest itinerary, process destinations in sorted order.

Python Rebuilding a trip from tickets

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 route has len(tickets) + 1 stops because a path through m edges visits m + 1 vertices (counting repeats).

Complexity. Checking the degrees is O(V + E). Hierholzer visits every edge once, so it is O(V + E) time and O(V + E) space. There is no catch: Euler paths are genuinely easy.

Fleury's algorithm: never burn your bridge

Hierholzer is the fast way to find an Euler path, but an older algorithm, Fleury's, is easier to explain, and it shows why a careless walk fails. Walk from a valid start vertex, always taking an unused edge, with one rule: do not cross a bridge unless you have no other choice. A bridge is an edge whose removal disconnects the remaining unused edges. If you cross it, you can never come back to the edges you left behind.

At each step:

  1. If the current vertex has exactly one unused edge, take it.
  2. Otherwise take an edge that is not a bridge of the unused-edge graph. When the current vertex still has two or more unused edges, at least one of them is not a bridge, so the rule never gets stuck.

Testing for a bridge by deleting the edge and searching again costs O(E), so the whole algorithm is O(E^2). That is why Hierholzer, at O(V + E), is used in practice, while Fleury stays a teaching tool.

Python Fleury's algorithm with a bridge test

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 first result starts at vertex 0, runs around the square and finishes on the diagonal, using all five edges. In the two-triangle graph the walk begins at 2, which has the bridge 2-3 among its edges. Fleury refuses to cross it while the triangle 0-1-2 still has unused edges, so it walks the first triangle, and only then crosses to the second. The four-odd-vertex star prints None.

The Chinese postman problem

A letter carrier must walk every street at least once and return to the post office, with as little walking as possible. If every vertex has even degree, an Euler circuit does it. Otherwise some streets must be walked twice. This is the Chinese postman (route inspection) problem, named after the Chinese mathematician Kwan Mei-Ko.

The odd-degree vertices always come in an even number (the handshake lemma), and they are the only places that cause trouble. The fix is to pair them up and add duplicate edges along a shortest path between each pair. After that, every vertex has even degree, and an Euler circuit exists. To minimise the total extra distance:

  1. Find the odd-degree vertices.
  2. Compute all-pairs shortest paths (see Floyd-Warshall).
  3. Find the minimum-weight perfect matching on the odd vertices. For a handful of odd vertices a bitmask DP does it; for large ones the blossom algorithm solves it in polynomial time.
  4. The answer is sum of all edge weights + weight of the matching.
Python Route inspection with a bitmask matching

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 map has two odd junctions, 1 and 2, and the cheapest way to pair them is the street between them (length 2), so the carrier walks 27 + 2 = 29. The ring has no odd vertices, so extra is 0 and the answer is just the sum of the streets. In the star, the four leaves are odd; the cheapest pairing is leaves (1, 2) at cost 3 plus leaves (3, 4) at cost 7, so the extra is 10 and the tour is 10 + 10 = 20. For directed streets (a one-way system) the problem still has a polynomial solution using min-cost flow, and with a mix of one-way and two-way streets it becomes NP-hard.

Hamiltonian paths: easy to state, hard to solve

Change "every edge" to "every vertex" and the problem flips. There is no known simple degree test for a Hamiltonian cycle, and no known algorithm that is polynomial in the size of the graph. Deciding whether one exists is NP-complete (see P, NP and hard problems).

Some partial results exist. Dirac's theorem says that a graph with n >= 3 vertices where every vertex has degree at least n / 2 always has a Hamiltonian cycle. Those are sufficient conditions, not exact tests. The general case needs search.

The straightforward method is backtracking: extend a path one vertex at a time, never reusing a vertex, and undo the step when you hit a dead end. In the worst case this examines all n! orderings.

Python Hamiltonian path by backtracking

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 graphs with a few dozen vertices the search is often fine because dead ends are detected early (pruning). For general graphs it explodes: with 20 vertices there are already about 2.4 quintillion orderings.

Travelling salesperson: the weighted cousin

Give every edge a distance and ask for the shortest tour that visits every city exactly once and returns home. That is the travelling salesperson problem (TSP): the shortest Hamiltonian cycle in a complete weighted graph.

The brute force tries every ordering of the other n - 1 cities, so (n - 1)! tours. For 12 cities that is already 39,916,800. A smarter method is dynamic programming over subsets (the Held-Karp algorithm): let best[mask][last] be the shortest route that starts at city 0, visits exactly the cities in the bitmask mask, and ends at last. Extending from last to a new city nxt not in the mask gives:

TEXT
best[mask | 1<<nxt][nxt] = min(best[mask][last] + dist[last][nxt])

There are 2^n * n states and each is extended in n ways, so the time is O(2^n * n^2) instead of O(n!). That is still exponential, but it handles about 20 cities instead of 11. The full technique is the topic of bitmask DP; here is a small preview next to the brute force it replaces.

Python TSP: brute force versus bitmask DP

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.

Both methods agree. The brute force checks 4! = 24 tours here; Held-Karp uses 2^5 * 5 = 160 states, which looks bigger, but the gap reverses quickly as n grows.

Euler versus Hamiltonian at a glance

Euler path Hamiltonian path
Visits every edge once every vertex once
Existence test degree parity + connectivity no simple test (NP-complete)
Algorithm Hierholzer, O(V + E) search, exponential in the worst case
Typical use route inspection, DNA assembly, ticket itineraries scheduling, puzzles, tours (TSP)

A famous bridge between the two: de Bruijn sequences and genome assembly turn a Hamiltonian-looking problem (find a string containing every k-mer) into an Euler path problem, which makes it solvable in linear time.

Common mistakes

  • Forgetting connectivity. Even degrees are not enough if the edges live in two separate pieces.
  • Counting degree in a multigraph wrongly. Parallel edges each add one to the degree (Konigsberg has two A-B bridges).
  • Starting Hierholzer at the wrong vertex. If two vertices have odd degree (or out - in = 1), you must start at one of them.
  • Mutating the adjacency list while another loop iterates it. Pop from the lists inside the stack loop only.
  • Assuming Hamiltonian is "just like Euler". Cheap tricks for one do not transfer; do not expect a linear algorithm for the other.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. An undirected connected graph has exactly two vertices of odd degree. What does it have?

    Walks pair up edges at inner vertices, so only the start and end may have an odd number of edges.
  2. 2. What is the time complexity of Hierholzer's algorithm?

    Every edge is removed from the adjacency list exactly once and every vertex is pushed and popped a bounded number of times.
  3. 3. Why can the Konigsberg bridge walk not exist?

    All four vertices have odd degree (5, 3, 3, 3), and an Euler path allows at most two.
  4. 4. Which statement about Hamiltonian cycles is true?

    No polynomial algorithm is known; the degree rule belongs to Euler circuits, not Hamiltonian cycles.
  5. 5. How does the Held-Karp bitmask DP compare with brute-force TSP?

    It still grows exponentially, but far slower than factorial, so about 20 cities become feasible instead of about 11.

Summary

  • An Euler path uses every edge once; a Hamiltonian path visits every vertex once.
  • Euler existence is a degree test (all even for a circuit, exactly two odd for a path; in/out balance for directed graphs) plus connectivity.
  • Hierholzer's algorithm builds the path in O(V + E) with a stack, writing vertices down when they are finished and reversing at the end.
  • Fleury's algorithm walks edge by edge and avoids bridges until forced; it is O(E^2), so Hierholzer is preferred in practice.
  • The Chinese postman problem pairs up the odd-degree vertices with shortest paths (minimum-weight matching) and adds the matching weight to the total street length.
  • Hamiltonian paths and TSP are NP-hard; backtracking works for small graphs and Held-Karp bitmask DP reduces n! to O(2^n * n^2).
  • Tickets, route inspection and genome assembly are real Euler problems; scheduling and tours are Hamiltonian ones.

Next: Dynamic Programming