Euler & Hamiltonian Paths
Why this exists
Two questions look almost identical. Can I walk through the graph using every edge exactly once? Can I walk through the graph visiting every vertex exactly once? The first is an Euler path question and is answered in by counting degrees and running one clever DFS. The second is a Hamiltonian path question and is NP-complete: no polynomial algorithm is known, and finding one would settle P versus NP. The contrast is one of the most instructive in all of algorithms. A one-word change in the problem statement moves you from "linear time, any size" to "exponential time, or so", and recognising which one you are facing is the whole skill.
Euler paths are where graph theory began. In 1736 Leonhard Euler showed that no walk through Königsberg crosses each of its seven bridges exactly once, and in doing so introduced the idea that only the degrees of the land masses matter. The constructive half — an algorithm that actually builds the walk when one exists — came from Carl Hierholzer, whose paper was published posthumously in 1873. Today Euler paths assemble genomes from short DNA reads (de Bruijn graph assemblers), generate test sequences that exercise every transition of a state machine, plan routes for snow ploughs and mail carriers (the Chinese postman problem), and produce the shortest string containing every PIN code as a substring.
Hamiltonian paths carry the name of William Rowan Hamilton, who in 1857 sold a puzzle, the "Icosian game", asking for a cycle through all twenty vertices of a dodecahedron. The knight's tour — a knight visiting every square of a chessboard once — is a Hamiltonian path on the knight-move graph, studied by Euler himself in 1759. The optimisation version, the travelling salesman problem, is the archetypal hard problem of operations research. This lesson gives you the exact dynamic programme that is the standard answer for small , the backtracking and pruning that work in practice a little beyond that, the classic sufficient conditions, and Warnsdorff's 200-year-old heuristic that finds knight's tours almost instantly. It builds on DFS and on the degree and connectivity reasoning from connectivity.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "use every edge / road / ticket / domino exactly once" | Euler path or circuit |
| "visit every vertex / city / cell exactly once" | Hamiltonian path — exponential; check |
| "return to the start" with every edge once | Euler circuit: all degrees even (undirected) / in = out (directed) |
| A list of pairs to chain end-to-start ("arrange pairs", "dominoes", "words where last letter = next first letter") | Directed Euler path on symbols |
| "lexicographically smallest itinerary using all tickets" | Hierholzer with sorted adjacency |
| "shortest string containing every length- string over symbols" | de Bruijn sequence = Euler circuit on -length nodes |
| "reconstruct the string from all its length-3 substrings" | Euler path on 2-character nodes |
| "traverse every edge at least once, minimum total length" | Chinese postman: Euler + matching of odd vertices |
| and "visit all", "order of cities", "shortest route through all" | Bitmask DP over subsets, |
| or heavy constraints, "count arrangements" | Backtracking with pruning |
| Knight's tour, "visit each square once" on a board | Warnsdorff's rule (+ backtracking fallback) |
| Dense graph, "prove a Hamiltonian cycle exists" | Dirac / Ore sufficient conditions |
| in the thousands and "visit all vertices exactly once" with no special structure | You misread, or it is a special graph (tournament, grid, complete) — or the intended answer is a heuristic |
The single most important trigger: edges → Euler, linear; vertices → Hamilton, exponential.
Intuition & first principles
Why only degrees matter for Euler
Walk along an Euler trail and watch any vertex that is neither the start nor the end. Every time the trail arrives at along one edge, it must leave along another. So the edges at are used in arrive/leave pairs, and must be even. The start vertex has one extra "leave" and the end one extra "arrive", so they are the only vertices allowed to be odd — and if the trail is a closed circuit, start = end and everybody is even. That is the necessary condition, and it needs nothing but counting.
The surprising half is that the condition is also sufficient (plus connectivity): if every vertex has even degree and the edges form one connected piece, an Euler circuit exists. The intuition is that you cannot get stuck anywhere except at home. Start at and walk, never reusing an edge. Whenever you enter a vertex , you have used an odd number of its edges, and its degree is even, so an unused edge remains to leave by. You can only get stuck at . The closed walk you get might miss some edges, but at some vertex on it there is an unused edge (connectivity), and the leftover graph still has all degrees even (you removed a closed walk, which uses edges in pairs at every vertex). So walk another closed loop from there and splice it in. Repeat. That splicing is Hierholzer's algorithm.
Directed graphs: arrivals and departures
In a directed graph the arrive/leave pairing is literal: every pass through uses one incoming and one outgoing edge. So a directed Euler circuit needs everywhere, and a directed Euler path needs that everywhere except at a start with and an end with .
Why vertices are different
Try the same reasoning for Hamiltonian paths. Is there a local condition — something checkable at each vertex — that guarantees a path through all vertices? Visiting uses exactly two of its edges and forbids all the others from being used to reach again; whether that is fine depends on choices made elsewhere in the graph. There is no splicing trick: two cycles that each cover half the vertices cannot be merged into one without global rearrangement. This lack of locality is what NP-completeness formalises. Richard Karp listed both the directed and undirected Hamiltonian circuit problems among his 21 NP-complete problems in 1972. Practically, it means exact algorithms are exponential in , and the craft is in making the exponent small: instead of , which is the difference between and at .
The precise statement behind the analogy
"You can only get stuck at home" is the lemma: in a graph where every vertex has even degree, a walk from that never repeats an edge can only terminate at . Hierholzer's algorithm builds closed walks with this lemma and splices them; the splicing is implicit in the order a stack pops vertices.
Mechanics
Euler path and circuit conditions
Ignore isolated vertices (degree 0); they do not affect whether the edges can be traversed.
| Graph | Euler circuit exists iff | Euler path (not closed) exists iff | Start at |
|---|---|---|---|
| Undirected | connected (non-isolated part) and every degree even | connected and exactly two odd-degree vertices | one of the odd vertices |
| Directed | weakly connected and for all | weakly connected, one vertex with , one with , all others balanced | the vertex with |
An undirected graph can never have exactly one odd vertex (the sum of degrees is , even). For directed graphs, weak connectivity (connected when directions are ignored) is enough together with the degree condition: balanced degrees plus weak connectivity force strong connectivity. I checked both tables against a brute force that tries every edge ordering on all random multigraphs with up to 4 vertices and 5 edges.
Hierholzer's algorithm, iterative
The iterative form uses a stack and an output list:
- Push the start vertex.
- Look at the top vertex . If it has an unused edge , mark the edge used and push .
- Otherwise, pop and append it to the output.
- Repeat until the stack is empty. The output reversed is the Euler path.
Each vertex keeps a pointer into its adjacency list, so "find an unused edge" never rescans edges already passed over. For undirected graphs each edge appears in two adjacency lists, so mark it used by edge id and skip used entries.
flowchart TD
S["push start"] --> T{"top u has an unused edge?"}
T -->|"yes"| P["mark edge u-v used, push v"]
P --> T
T -->|"no"| O["pop u, append to output"]
O --> Q{"stack empty?"}
Q -->|"no"| T
Q -->|"yes"| R["reverse output = Euler path"]
Why does this splice cycles correctly? The stack is always a trail from the start. Pushing extends the trail greedily. When the top vertex runs out of edges, it is "stuck at home" for whatever closed loop it is on; popping it commits it to the answer and backs up to the most recent vertex that still has unused edges, from which a new loop is explored. Because a vertex is appended only after all loops through it have been explored, those loops end up nested inside the output in the right place. The proof below makes this exact.
Trace: a bow-tie
Two triangles sharing vertex 1: edges in input order . Degrees are — all even, so an Euler circuit exists. Start at 0.
flowchart LR
V0(("0")) ---|"e0"| V1(("1"))
V1 ---|"e1"| V2(("2"))
V2 ---|"e2"| V0
V1 ---|"e3"| V3(("3"))
V3 ---|"e4"| V4(("4"))
V4 ---|"e5"| V1
Computed by running the algorithm and logging every push and pop:
| Step | Action | Stack (bottom → top) | Output so far |
|---|---|---|---|
| 0 | start | 0 | |
| 1 | 0 uses e0, push 1 | 0 1 | |
| 2 | 1 uses e1, push 2 | 0 1 2 | |
| 3 | 2 uses e2, push 0 | 0 1 2 0 | |
| 4 | 0 has no unused edge: pop | 0 1 2 | 0 |
| 5 | 2 has no unused edge: pop | 0 1 | 0 2 |
| 6 | 1 uses e3, push 3 | 0 1 3 | 0 2 |
| 7 | 3 uses e4, push 4 | 0 1 3 4 | 0 2 |
| 8 | 4 uses e5, push 1 | 0 1 3 4 1 | 0 2 |
| 9 | 1 stuck: pop | 0 1 3 4 | 0 2 1 |
| 10 | pop 4 | 0 1 3 | 0 2 1 4 |
| 11 | pop 3 | 0 1 | 0 2 1 4 3 |
| 12 | pop 1 | 0 | 0 2 1 4 3 1 |
| 13 | pop 0 | (empty) | 0 2 1 4 3 1 0 |
Reversed: 0 → 1 → 3 → 4 → 1 → 2 → 0. Look at what happened. The greedy walk first found the closed loop , which misses the right triangle. Steps 4–5 popped 0 and 2 because they were finished. At step 6 vertex 1 still had edges, so a second loop was explored from it. In the reversed output, that loop appears exactly where vertex 1 sits in the first loop: the splice happened automatically.
Handling the start vertex
- Undirected path: start at an odd vertex. Starting at an even vertex when two odd ones exist is a silent bug: the output still has vertices, but it is not a trail — somewhere two consecutive vertices are not joined by an edge. In a random test of about 7,000 such graphs, every wrong-start output had the right length and none was valid, so the length check below cannot catch it.
- Directed path: start at the vertex with .
- Circuit: any vertex with nonzero degree. Do not start at an isolated vertex, or you will output a one-vertex "path" for a graph full of edges.
- Fixed start and end (CSES "Mail Delivery" fixes vertex 1; "Teleporters Path" fixes ): check that the degrees permit exactly that start and end before running.
After the run, check that the output has vertices. If it is shorter, the edges were not connected, and no Euler path exists. This one length check replaces a separate connectivity test.
Reconstruct itinerary: lexicographic Euler paths
LeetCode 332 gives airline tickets as directed edges and asks for the itinerary that uses all tickets, starts at JFK, and is lexicographically smallest. Sort each adjacency list and always take the smallest unused edge. It is tempting to think greedy choice can paint you into a corner — and it can, for the walk: from JFK with tickets to KUL and NRT and a ticket NRT → JFK, greedily going to KUL first gets stuck. But Hierholzer does not commit to the walk; it commits to the pop order. KUL is popped first and lands at the end of the reversed output, and the loop through NRT is spliced before it: JFK → NRT → JFK → KUL. Sorting plus Hierholzer gives the lexicographically smallest Euler path. (The informal argument: at each vertex, the output takes the smallest edge whose removal does not disconnect the remaining edges from the eventual end — which is exactly what the splice achieves. A full proof is fiddly; the result is standard and tested below.)
De Bruijn sequences
A de Bruijn sequence is a cyclic string over an alphabet of size in which every length- string appears exactly once as a substring. Written linearly (unwrapped), it has length , which is optimal: there are strings to cover and each new character can complete at most one new window.
Build it as an Euler circuit. Make one vertex per string of length ( vertices). From vertex , for each symbol , add an edge to , labelled with the length- string . Every vertex has in-degree and out-degree , and the graph is strongly connected (you can reach any string by appending its characters), so an Euler circuit exists. It uses each of the edges once, i.e. each length- window once. For the construction below produces 0001011100: its windows 000, 001, 010, 101, 011, 111, 110, 100 are all eight binary triples.
flowchart LR
A(("00")) -->|"0"| A
A -->|"1"| B(("01"))
B -->|"0"| C(("10"))
B -->|"1"| D(("11"))
C -->|"0"| A
C -->|"1"| B
D -->|"0"| C
D -->|"1"| D
This is LeetCode 753 "Cracking the Safe" (the shortest sequence of key presses that tries every -digit code) and CSES "De Bruijn Sequence". The number of distinct de Bruijn sequences is — for binary, , i.e. 1, 2 and 16 for , which my brute force confirms — a consequence of the BEST theorem for counting Euler circuits (de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte).
Chinese postman: every edge at least once
If the graph has odd vertices, no Euler circuit exists — but a mail carrier still needs to walk every street and return. The Chinese postman problem (posed by Mei-Ko Kwan in 1962) asks for the shortest closed walk using every edge at least once. The answer: duplicate some edges so that every degree becomes even, minimising the total length of duplicated edges, then take an Euler circuit. The odd vertices come in an even number; pair them up so the sum of shortest-path distances between partners is minimal. That is a minimum-weight perfect matching on the odd vertices (Edmonds and Johnson, 1973), polynomial time. With only two odd vertices it is just "add the shortest path between them". The directed version is a min-cost flow; the mixed version (some one-way streets) is NP-hard.
Hamiltonian paths: bitmask DP
Let be the number of paths that start at vertex 0, visit exactly the vertex set (as a bitmask, ), and end at . Then
The answer to "how many Hamiltonian paths from 0 to " is ; "does a Hamiltonian path exist" uses booleans and any start; the travelling salesman problem replaces counting with of costs (Bellman 1962; Held and Karp 1962). There are states and each processes up to outgoing edges, so time and memory. For that is about elementary steps and states — the reason contest problems with "visit all" cap at about 20. The Bitmask DP: TSP & Assignment lesson in Module 6 (Dynamic Programming) develops this family in depth.
flowchart LR
A["mask 0001, at 0 : 1 way"] -->|"0 to 1, two edges"| B["mask 0011, at 1 : 2"]
A -->|"0 to 2"| C["mask 0101, at 2 : 1"]
B -->|"1 to 2"| D["mask 0111, at 2 : 2"]
C -->|"2 to 1"| E["mask 0111, at 1 : 1"]
D -->|"2 to 3"| F["mask 1111, at 3 : 3"]
E -->|"1 to 3"| F
Trace: counting Hamiltonian paths
Directed multigraph on 4 vertices with edges (twice), , , , , . Count paths through all vertices. Non-zero states, computed by the DP, in increasing mask order (bit = vertex , written with vertex 3 on the left):
| Mask | Vertices | (non-zero) | Where it came from |
|---|---|---|---|
| 0001 | {0} | end 0: 1 | base case |
| 0011 | {0,1} | end 1: 2 | two parallel edges |
| 0101 | {0,2} | end 2: 1 | |
| 0111 | {0,1,2} | end 1: 1, end 2: 2 | from (0101, 2); from (0011, 1) |
| 1011 | {0,1,3} | end 3: 2 | from (0011, 1) — a dead end, 2 is unvisited |
| 1101 | {0,2,3} | end 3: 1 | from (0101, 2) — dead end |
| 1111 | all | end 3: 3 | from (0111, 2) gives 2, from (0111, 1) gives 1 |
The three paths are (counted twice, once per parallel edge) and . Rows 1011 and 1101 are wasted work: they reached vertex 3 too early. The CSES-style optimisation skips any state containing the final vertex unless the mask is full, which cuts the work roughly in half.
Backtracking with pruning
For up to about 12 (or larger when the graph is sparse), plain DFS over partial paths with good pruning beats the DP's memory:
- Degree pruning: an unvisited vertex with no unvisited neighbour other than the current end can only be the final vertex; if two such vertices exist, backtrack.
- Connectivity pruning: if the unvisited vertices are not connected (via BFS) to each other and to the current end, backtrack.
- Order heuristics: try neighbours with the fewest onward options first (the same idea as Warnsdorff below); it finds a solution sooner when one exists, though it does not help prove non-existence.
- Fixed endpoints: if the problem fixes the end vertex, never enter it before the last step.
Sufficient conditions: Dirac and Ore
Since no efficient test exists, sufficient conditions are valuable. For a simple undirected graph on vertices:
- Dirac (1952): if every vertex has degree , the graph has a Hamiltonian cycle.
- Ore (1960): if for every pair of non-adjacent vertices , the graph has a Hamiltonian cycle. Dirac's theorem is the special case where every degree is at least .
These are sufficient, not necessary: a cycle graph is Hamiltonian with every degree 2. Their proofs are constructive (a rotation argument that repairs a Hamiltonian path into a cycle) and give algorithms to find the cycle when the condition holds. Two more facts worth knowing: every tournament (complete graph with each edge oriented one way) has a Hamiltonian path (Rédei, 1934), found by insertion sort with "beats" as the comparison; and every complete graph trivially has one, which is why TSP is about cost, not existence.
Knight's tour and Warnsdorff's rule
A knight's tour is a Hamiltonian path in the graph whose vertices are squares and whose edges are knight moves. On the graph has 64 vertices — far too many for the bitmask DP — yet tours are easy to find, because of Warnsdorff's rule (H. C. von Warnsdorf, 1823): always move to the square with the fewest onward unvisited moves. The intuition is that squares with few exits (corners, edges) will become unreachable if postponed, so visit them while you still can. Pure Warnsdorff, with ties broken by the first minimum in a fixed move order, succeeded from 63 of the 64 starting squares on in my test; wrapping it in backtracking (try candidates in Warnsdorff order, undo on failure) found a tour from all 64 in a fraction of a second in total. The rule is a heuristic: it is not guaranteed, and on larger boards pure Warnsdorff fails more often unless ties are broken more carefully (Squirrel and Cull, 1996, give tie-breaking rules that work up to very large boards). For the record, the number of undirected closed knight's tours on was computed by Brendan McKay in 1997 as 13,267,364,410,532.
The ladder: brute force → better → optimal
Euler paths
Rung 1 — try all edge orders, . Correct and useless beyond 10 edges. It is the brute force the degree conditions were checked against.
Rung 2 — Fleury's algorithm, or . Walk from a valid start; at each step take any edge that is not a bridge of the remaining graph unless it is the only option. Correct (you never cut yourself off from unused edges), but each step needs a bridge test — a full low-link DFS — so it is quadratic. Fleury (1883) is pleasant for hand simulation and appears in textbooks for that reason.
Rung 3 — Hierholzer, recursive, . Walk greedily, splice loops. Linear, but the recursion depth equals the path length, up to — deep crashes Python and Java.
Rung 4 — Hierholzer, iterative, . The stack version above. What to submit.
Hamiltonian paths
Rung 1 — all permutations, . is fine; is not.
Rung 2 — backtracking with pruning. Same worst case, but sparse graphs and early dead ends cut the tree drastically. Good for –15 in practice, and for "find one" on structured graphs (knight's tours) with good ordering.
Rung 3 — bitmask DP, time, memory. The paths that end at having visited are interchangeable for the future, so merge them. : about steps.
Rung 4 — beyond. Björklund (2010) gave an randomised algorithm for undirected Hamiltonicity using algebraic sieving; inclusion–exclusion counts Hamiltonian cycles in time with only polynomial memory. For TSP in practice, branch-and-cut solvers (Concorde) solve instances with tens of thousands of cities to optimality, and heuristics (Lin–Kernighan) get within a few percent on millions. None is polynomial in the worst case.
| Problem | Approach | Time | Memory | Practical limit |
|---|---|---|---|---|
| Euler | All edge orders | |||
| Euler | Fleury | |||
| Euler | Hierholzer (iterative) | |||
| Hamilton | All permutations | |||
| Hamilton | Backtracking + pruning | exponential, input-dependent | –15 general | |
| Hamilton / TSP | Bitmask DP | |||
| Knight's tour | Warnsdorff (+ backtracking) | ~ when it succeeds | boards in the hundreds per side |
Correctness
Necessity of the degree conditions
Let be an Euler trail from to . Each occurrence of an internal vertex on accounts for two edge-ends at (arrive, leave), and every edge-end at is used exactly once, so is even for . If , and each get one extra edge-end, making them odd; if , the first departure and last arrival pair up and is even. All edges lie on one walk, so the non-isolated vertices are connected. The directed version counts incoming and outgoing edge-ends separately. ∎
Sufficiency (constructive) and Hierholzer's correctness
Lemma (stuck only at home). If every vertex has even degree (directed: balanced), a trail that starts at and is extended until no unused edge leaves its endpoint ends at .
Proof. Suppose it is stuck at . Each earlier visit to used an arrive and a leave edge; the final arrival used one more. So an odd number of 's edges are used, but is even, so an unused edge remains. Contradiction. (Directed: arrivals at exceed departures by one, but in = out, so an unused outgoing edge remains.) ∎
Step 1: the first pop leaves an all-even remainder. The stack is always a trail from the start (each push uses a new edge). The first time the top vertex has no unused edge, all of 's edges are on that trail. A trail uses an odd number of edge-ends at an endpoint different from its start and an even number at internal vertices, so either (circuit case, all degrees even) or is the other odd vertex (path case, odd). Either way, after deleting the used edges every vertex has even remaining degree. (Directed: every vertex is balanced in the unused edges.)
Step 2: consecutive pops are adjacent. Claim: if is popped and is the vertex directly below it on the stack, the next vertex popped is a copy of . After 's pop, is on top. Either has no unused edge and is popped immediately, or a new excursion starts at using only unused edges; those form an all-even graph (step 1, and removing a closed walk keeps every degree even), so by the lemma the excursion can only get stuck back at , and the first vertex popped is that copy of . Hence every pair of consecutive output vertices is joined by the edge that pushed , each pushed edge is accounted for exactly once, and the reversed output is a trail through all used edges. Finally, a vertex is popped only when it has no unused edge, so when the stack empties no vertex on the trail has an unused edge; if the edges are connected, every edge is therefore used and the trail is an Euler path or circuit. If they are not, edges in another component stay unused — exactly what the output-length check detects. ∎
Step 1 is where the start vertex matters. Start at an even vertex while two odd ones exist and the remainder after the first pop has two odd vertices, so an excursion can get stuck away from home and step 2 fails: the output has the right length but contains a jump, the silent bug described above.
Why Hierholzer is
Charge every operation to an edge or a vertex. Each push uses a new edge (at most pushes, plus the initial one). Each pop removes a pushed vertex (at most pops). Finding the next unused edge advances a per-vertex pointer that never moves backwards; across the whole run the pointers advance a total of positions (undirected) or (directed), including skips over already-used entries. Initialisation is . Total . The pointer is essential: rescanning each adjacency list from the start every time would make dense vertices quadratic. ∎
Bitmask DP correctness
Induction on . Every path from 0 visiting exactly and ending at (with ) has a unique last edge ; removing leaves a path from 0 visiting exactly and ending at . Conversely, extending such a path by an edge with gives a valid path. So , which is what the forward "push" formulation computes, since every subset is processed after all its proper subsets (numerically smaller masks). Parallel edges count separately because each is a separate term. ∎
Why Hamiltonian path is hard (statement only)
Hamiltonian path and cycle, directed and undirected, are NP-complete: they are in NP (a proposed ordering is checked in ), and 3-SAT reduces to them by gadget constructions (Karp, 1972; Garey and Johnson, Computers and Intractability, problems GT37–GT39). The reduction and what NP-completeness does and does not imply are covered in the Complexity Theory: P, NP, NP-Completeness & Approximation lesson of Module 9 (Advanced Topics). For this lesson the practical consequence is enough: expect exponential algorithms, and read the constraints for a small or special structure.
Complexity
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Degree / balance check | |||
| Hierholzer (directed or undirected) | Pointer per vertex; used-flag per edge (undirected) | ||
| Lexicographic Hierholzer | Sorting adjacency lists dominates | ||
| de Bruijn | vertices + implicit edges | Output length | |
| Chinese postman (undirected) | matching + shortest paths | Blossom algorithm on odd vertices | |
| Hamiltonian bitmask DP | , or with adjacency lists | : 20 M states | |
| Backtracking | worst case | Input-dependent; pruning matters | |
| Warnsdorff knight's tour | when no backtracking is needed | Heuristic |
Best, average and worst coincide for Hierholzer: every edge is touched a constant number of times. For the bitmask DP the dominant cost is memory traffic: for with 32-bit entries is bytes = 80 MB, beyond most caches, so iterate masks in increasing order (sequential access) and keep the inner loop over the end vertex contiguous (dp[mask][v] with v as the fast index). In Python, states is too slow in pure loops; NumPy vectorisation over masks or a compiled language is needed for .
Implementation
Euler paths with Hierholzer (directed and undirected)
Both functions return a list of vertices, or an empty list / None when no Euler path exists. They check the degree conditions, choose the start, run iterative Hierholzer and verify the length (which catches disconnected edge sets). Tests (same in all four languages): the bow-tie circuit [0, 1, 3, 4, 1, 2, 0]; a triangle with a tail, undirected [0, 1, 2, 0, 3]; the same edges directed, [0, 1, 2, 0, 3]; two disjoint triangles (no path); a directed "fork" (no path).
def euler_path_undirected(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
if not edges:
return [0] if n else []
adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
deg = [0] * n
for i, (u, v) in enumerate(edges):
adj[u].append((v, i))
adj[v].append((u, i))
deg[u] += 1
deg[v] += 1
odd = [v for v in range(n) if deg[v] % 2 == 1]
if len(odd) not in (0, 2):
return None
start = odd[0] if odd else next(v for v in range(n) if deg[v] > 0)
used = [False] * len(edges)
ptr = [0] * n
stack, path = [start], []
while stack:
u = stack[-1]
while ptr[u] < len(adj[u]) and used[adj[u][ptr[u]][1]]:
ptr[u] += 1 # skip edges already used from the other end
if ptr[u] == len(adj[u]):
path.append(stack.pop())
else:
v, i = adj[u][ptr[u]]
used[i] = True
stack.append(v)
if len(path) != len(edges) + 1:
return None # edges not connected
return path[::-1]
def euler_path_directed(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
if not edges:
return [0] if n else []
adj: list[list[int]] = [[] for _ in range(n)]
bal = [0] * n # out - in
for u, v in edges:
adj[u].append(v)
bal[u] += 1
bal[v] -= 1
plus = [v for v in range(n) if bal[v] == 1]
minus = [v for v in range(n) if bal[v] == -1]
if any(abs(b) > 1 for b in bal) or len(plus) > 1 or len(minus) > 1 or len(plus) != len(minus):
return None
start = plus[0] if plus else next(v for v in range(n) if adj[v])
ptr = [0] * n
stack, path = [start], []
while stack:
u = stack[-1]
if ptr[u] < len(adj[u]):
stack.append(adj[u][ptr[u]])
ptr[u] += 1
else:
path.append(stack.pop())
if len(path) != len(edges) + 1:
return None
return path[::-1]
if __name__ == "__main__":
bowtie = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 1)]
tail = [(0, 1), (1, 2), (2, 0), (0, 3)]
assert euler_path_undirected(5, bowtie) == [0, 1, 3, 4, 1, 2, 0]
assert euler_path_undirected(4, tail) == [0, 1, 2, 0, 3]
assert euler_path_directed(4, tail) == [0, 1, 2, 0, 3]
assert euler_path_undirected(6, [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]) is None
assert euler_path_directed(3, [(0, 1), (0, 2)]) is None
print("hierholzer: all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Hierholzer {
/** Returns the Euler path as a vertex list, or null if none exists. */
static List<Integer> undirected(int n, int[][] edges) {
int m = edges.length;
if (m == 0) return n > 0 ? List.of(0) : List.of();
int[] deg = new int[n];
for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
int[] start = new int[n + 1];
for (int i = 0; i < n; i++) start[i + 1] = start[i] + deg[i];
int[] to = new int[2 * m], id = new int[2 * m], fill = Arrays.copyOf(start, n);
for (int i = 0; i < m; i++) {
int u = edges[i][0], v = edges[i][1];
to[fill[u]] = v; id[fill[u]++] = i;
to[fill[v]] = u; id[fill[v]++] = i;
}
int odd = 0, first = -1, firstOdd = -1;
for (int v = 0; v < n; v++) {
if (deg[v] % 2 == 1) { odd++; if (firstOdd < 0) firstOdd = v; }
if (deg[v] > 0 && first < 0) first = v;
}
if (odd != 0 && odd != 2) return null;
int s = odd == 2 ? firstOdd : first;
boolean[] used = new boolean[m];
int[] ptr = Arrays.copyOf(start, n);
int[] stack = new int[m + 1];
int top = 0;
stack[top++] = s;
List<Integer> path = new ArrayList<>();
while (top > 0) {
int u = stack[top - 1];
while (ptr[u] < start[u + 1] && used[id[ptr[u]]]) ptr[u]++;
if (ptr[u] == start[u + 1]) {
path.add(stack[--top]);
} else {
used[id[ptr[u]]] = true;
stack[top++] = to[ptr[u]];
}
}
if (path.size() != m + 1) return null;
java.util.Collections.reverse(path);
return path;
}
static List<Integer> directed(int n, int[][] edges) {
int m = edges.length;
if (m == 0) return n > 0 ? List.of(0) : List.of();
int[] outDeg = new int[n], bal = new int[n];
for (int[] e : edges) { outDeg[e[0]]++; bal[e[0]]++; bal[e[1]]--; }
int[] start = new int[n + 1];
for (int i = 0; i < n; i++) start[i + 1] = start[i] + outDeg[i];
int[] to = new int[m], fill = Arrays.copyOf(start, n);
for (int[] e : edges) to[fill[e[0]]++] = e[1];
int plus = 0, minus = 0, s = -1, first = -1;
for (int v = 0; v < n; v++) {
if (Math.abs(bal[v]) > 1) return null;
if (bal[v] == 1) { plus++; s = v; }
if (bal[v] == -1) minus++;
if (outDeg[v] > 0 && first < 0) first = v;
}
if (plus > 1 || minus > 1 || plus != minus) return null;
if (s < 0) s = first;
int[] ptr = Arrays.copyOf(start, n);
int[] stack = new int[m + 1];
int top = 0;
stack[top++] = s;
List<Integer> path = new ArrayList<>();
while (top > 0) {
int u = stack[top - 1];
if (ptr[u] < start[u + 1]) stack[top++] = to[ptr[u]++];
else path.add(stack[--top]);
}
if (path.size() != m + 1) return null;
java.util.Collections.reverse(path);
return path;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[][] bowtie = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 1}};
int[][] tail = {{0, 1}, {1, 2}, {2, 0}, {0, 3}};
check(undirected(5, bowtie).equals(List.of(0, 1, 3, 4, 1, 2, 0)), "bowtie");
check(undirected(4, tail).equals(List.of(0, 1, 2, 0, 3)), "tail undirected");
check(directed(4, tail).equals(List.of(0, 1, 2, 0, 3)), "tail directed");
check(undirected(6, new int[][]{{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3}}) == null, "disconnected");
check(directed(3, new int[][]{{0, 1}, {0, 2}}) == null, "fork");
System.out.println("hierholzer: all tests passed");
}
}
#include <cassert>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>
using Edges = std::vector<std::pair<int, int>>;
std::optional<std::vector<int>> eulerUndirected(int n, const Edges& edges) {
int m = static_cast<int>(edges.size());
if (m == 0) return n ? std::vector<int>{0} : std::vector<int>{};
std::vector<std::vector<std::pair<int, int>>> adj(n);
std::vector<int> deg(n, 0);
for (int i = 0; i < m; ++i) {
auto [u, v] = edges[i];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
++deg[u];
++deg[v];
}
int odd = 0, firstOdd = -1, first = -1;
for (int v = 0; v < n; ++v) {
if (deg[v] % 2) { ++odd; if (firstOdd < 0) firstOdd = v; }
if (deg[v] > 0 && first < 0) first = v;
}
if (odd != 0 && odd != 2) return std::nullopt;
std::vector<char> used(m, 0);
std::vector<size_t> ptr(n, 0);
std::vector<int> stack{odd ? firstOdd : first}, path;
while (!stack.empty()) {
int u = stack.back();
while (ptr[u] < adj[u].size() && used[adj[u][ptr[u]].second]) ++ptr[u];
if (ptr[u] == adj[u].size()) {
path.push_back(u);
stack.pop_back();
} else {
auto [v, i] = adj[u][ptr[u]];
used[i] = 1;
stack.push_back(v);
}
}
if (static_cast<int>(path.size()) != m + 1) return std::nullopt;
return std::vector<int>(path.rbegin(), path.rend());
}
std::optional<std::vector<int>> eulerDirected(int n, const Edges& edges) {
int m = static_cast<int>(edges.size());
if (m == 0) return n ? std::vector<int>{0} : std::vector<int>{};
std::vector<std::vector<int>> adj(n);
std::vector<int> bal(n, 0);
for (auto [u, v] : edges) {
adj[u].push_back(v);
++bal[u];
--bal[v];
}
int plus = 0, minus = 0, s = -1, first = -1;
for (int v = 0; v < n; ++v) {
if (bal[v] > 1 || bal[v] < -1) return std::nullopt;
if (bal[v] == 1) { ++plus; s = v; }
if (bal[v] == -1) ++minus;
if (!adj[v].empty() && first < 0) first = v;
}
if (plus > 1 || minus > 1 || plus != minus) return std::nullopt;
if (s < 0) s = first;
std::vector<size_t> ptr(n, 0);
std::vector<int> stack{s}, path;
while (!stack.empty()) {
int u = stack.back();
if (ptr[u] < adj[u].size()) {
stack.push_back(adj[u][ptr[u]++]);
} else {
path.push_back(u);
stack.pop_back();
}
}
if (static_cast<int>(path.size()) != m + 1) return std::nullopt;
return std::vector<int>(path.rbegin(), path.rend());
}
int main() {
using V = std::vector<int>;
Edges bowtie{{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 1}};
Edges tail{{0, 1}, {1, 2}, {2, 0}, {0, 3}};
assert(eulerUndirected(5, bowtie) == (V{0, 1, 3, 4, 1, 2, 0}));
assert(eulerUndirected(4, tail) == (V{0, 1, 2, 0, 3}));
assert(eulerDirected(4, tail) == (V{0, 1, 2, 0, 3}));
assert(!eulerUndirected(6, {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3}}).has_value());
assert(!eulerDirected(3, {{0, 1}, {0, 2}}).has_value());
std::cout << "hierholzer: all tests passed\n";
}
function eulerUndirected(n: number, edges: [number, number][]): number[] | null {
const m = edges.length;
if (m === 0) return n > 0 ? [0] : [];
const adj: [number, number][][] = Array.from({ length: n }, () => []);
const deg = new Array<number>(n).fill(0);
edges.forEach(([u, v], i) => {
adj[u].push([v, i]);
adj[v].push([u, i]);
deg[u]++;
deg[v]++;
});
const odd = deg.map((d, v) => (d % 2 === 1 ? v : -1)).filter((v) => v >= 0);
if (odd.length !== 0 && odd.length !== 2) return null;
const start = odd.length ? odd[0] : deg.findIndex((d) => d > 0);
const used = new Array<boolean>(m).fill(false);
const ptr = new Array<number>(n).fill(0);
const stack: number[] = [start];
const path: number[] = [];
while (stack.length > 0) {
const u = stack[stack.length - 1];
while (ptr[u] < adj[u].length && used[adj[u][ptr[u]][1]]) ptr[u]++;
if (ptr[u] === adj[u].length) {
path.push(stack.pop() as number);
} else {
const [v, i] = adj[u][ptr[u]];
used[i] = true;
stack.push(v);
}
}
return path.length === m + 1 ? path.reverse() : null;
}
function eulerDirected(n: number, edges: [number, number][]): number[] | null {
const m = edges.length;
if (m === 0) return n > 0 ? [0] : [];
const adj: number[][] = Array.from({ length: n }, () => []);
const bal = new Array<number>(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
bal[u]++;
bal[v]--;
}
if (bal.some((b) => Math.abs(b) > 1)) return null;
const plus = bal.filter((b) => b === 1).length;
const minus = bal.filter((b) => b === -1).length;
if (plus > 1 || minus > 1 || plus !== minus) return null;
const start = plus ? bal.indexOf(1) : adj.findIndex((a) => a.length > 0);
const ptr = new Array<number>(n).fill(0);
const stack: number[] = [start];
const path: number[] = [];
while (stack.length > 0) {
const u = stack[stack.length - 1];
if (ptr[u] < adj[u].length) stack.push(adj[u][ptr[u]++]);
else path.push(stack.pop() as number);
}
return path.length === m + 1 ? path.reverse() : null;
}
const same = (a: unknown, b: unknown) => JSON.stringify(a) === JSON.stringify(b);
const bowtie: [number, number][] = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 1]];
const tail: [number, number][] = [[0, 1], [1, 2], [2, 0], [0, 3]];
if (!same(eulerUndirected(5, bowtie), [0, 1, 3, 4, 1, 2, 0])) throw new Error("bowtie");
if (!same(eulerUndirected(4, tail), [0, 1, 2, 0, 3])) throw new Error("tail undirected");
if (!same(eulerDirected(4, tail), [0, 1, 2, 0, 3])) throw new Error("tail directed");
if (eulerUndirected(6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3]]) !== null) throw new Error("disconnected");
if (eulerDirected(3, [[0, 1], [0, 2]]) !== null) throw new Error("fork");
console.log("hierholzer: all tests passed");
Counting Hamiltonian paths with bitmask DP
Counts directed paths from vertex 0 to vertex that visit every vertex exactly once, modulo , with parallel edges counted separately (the CSES "Hamiltonian Flights" model). It skips masks without vertex 0 and states that reach early. Tests: the 4-vertex example gives 3; a single edge gives 1; on 3 vertices gives 0 (the path must end at 2).
MOD = 10**9 + 7
def count_hamiltonian_paths(n: int, edges: list[tuple[int, int]]) -> int:
succ: list[list[int]] = [[] for _ in range(n)]
for a, b in edges:
succ[a].append(b)
full = (1 << n) - 1
last = n - 1
dp = [[0] * n for _ in range(1 << n)]
dp[1][0] = 1
for mask in range(1, 1 << n):
if not mask & 1:
continue # every path starts at 0
if mask >> last & 1 and mask != full:
continue # reached the end too early
row = dp[mask]
for v in range(n):
ways = row[v]
if ways == 0:
continue
for w in succ[v]:
if not mask >> w & 1:
nxt = mask | 1 << w
dp[nxt][w] = (dp[nxt][w] + ways) % MOD
return dp[full][last]
if __name__ == "__main__":
example = [(0, 1), (0, 1), (1, 2), (2, 3), (0, 2), (1, 3), (2, 1)]
assert count_hamiltonian_paths(4, example) == 3
assert count_hamiltonian_paths(2, [(0, 1)]) == 1
assert count_hamiltonian_paths(3, [(0, 2), (2, 1)]) == 0
print("hamiltonian path count: all tests passed")
import java.util.ArrayList;
import java.util.List;
public class HamiltonianCount {
static final int MOD = 1_000_000_007;
static int count(int n, int[][] edges) {
List<List<Integer>> succ = new ArrayList<>();
for (int i = 0; i < n; i++) succ.add(new ArrayList<>());
for (int[] e : edges) succ.get(e[0]).add(e[1]);
int full = (1 << n) - 1, last = n - 1;
int[][] dp = new int[1 << n][n];
dp[1][0] = 1;
for (int mask = 1; mask <= full; mask++) {
if ((mask & 1) == 0) continue;
if ((mask >> last & 1) == 1 && mask != full) continue;
for (int v = 0; v < n; v++) {
int ways = dp[mask][v];
if (ways == 0) continue;
for (int w : succ.get(v)) {
if ((mask >> w & 1) == 0) {
int nxt = mask | 1 << w;
dp[nxt][w] = (dp[nxt][w] + ways) % MOD;
}
}
}
}
return dp[full][last];
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
int[][] example = {{0, 1}, {0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 1}};
check(count(4, example) == 3, "example");
check(count(2, new int[][]{{0, 1}}) == 1, "single edge");
check(count(3, new int[][]{{0, 2}, {2, 1}}) == 0, "wrong end");
System.out.println("hamiltonian path count: all tests passed");
}
}
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
int countHamiltonianPaths(int n, const std::vector<std::pair<int, int>>& edges) {
const int MOD = 1'000'000'007;
std::vector<std::vector<int>> succ(n);
for (auto [a, b] : edges) succ[a].push_back(b);
int full = (1 << n) - 1, last = n - 1;
std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, 0));
dp[1][0] = 1;
for (int mask = 1; mask <= full; ++mask) {
if (!(mask & 1)) continue;
if ((mask >> last & 1) && mask != full) continue;
for (int v = 0; v < n; ++v) {
int ways = dp[mask][v];
if (!ways) continue;
for (int w : succ[v]) {
if (!(mask >> w & 1)) {
int nxt = mask | 1 << w;
dp[nxt][w] = (dp[nxt][w] + ways) % MOD;
}
}
}
}
return dp[full][last];
}
int main() {
assert(countHamiltonianPaths(4, {{0, 1}, {0, 1}, {1, 2}, {2, 3}, {0, 2}, {1, 3}, {2, 1}}) == 3);
assert(countHamiltonianPaths(2, {{0, 1}}) == 1);
assert(countHamiltonianPaths(3, {{0, 2}, {2, 1}}) == 0);
std::cout << "hamiltonian path count: all tests passed\n";
}
const HAM_MOD = 1_000_000_007;
function countHamiltonianPaths(n: number, edges: [number, number][]): number {
const succ: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) succ[a].push(b);
const full = (1 << n) - 1;
const last = n - 1;
const dp: Int32Array[] = Array.from({ length: 1 << n }, () => new Int32Array(n));
dp[1][0] = 1;
for (let mask = 1; mask <= full; mask++) {
if ((mask & 1) === 0) continue;
if (((mask >> last) & 1) === 1 && mask !== full) continue;
for (let v = 0; v < n; v++) {
const ways = dp[mask][v];
if (ways === 0) continue;
for (const w of succ[v]) {
if (((mask >> w) & 1) === 0) {
const nxt = mask | (1 << w);
dp[nxt][w] = (dp[nxt][w] + ways) % HAM_MOD; // < 2^31, safe in Int32Array
}
}
}
}
return dp[full][last];
}
if (countHamiltonianPaths(4, [[0, 1], [0, 1], [1, 2], [2, 3], [0, 2], [1, 3], [2, 1]]) !== 3) throw new Error("example");
if (countHamiltonianPaths(2, [[0, 1]]) !== 1) throw new Error("single edge");
if (countHamiltonianPaths(3, [[0, 2], [2, 1]]) !== 0) throw new Error("wrong end");
console.log("hamiltonian path count: all tests passed");
Variant: reconstruct itinerary (lexicographically smallest)
from collections import defaultdict
def find_itinerary(tickets: list[list[str]], start: str = "JFK") -> list[str]:
graph: dict[str, list[str]] = defaultdict(list)
for a, b in sorted(tickets, reverse=True): # reverse-sorted so pop() yields the smallest
graph[a].append(b)
stack, out = [start], []
while stack:
while graph[stack[-1]]:
stack.append(graph[stack[-1]].pop())
out.append(stack.pop())
return out[::-1]
assert find_itinerary([["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]) == \
["JFK", "MUC", "LHR", "SFO", "SJC"]
assert find_itinerary([["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]) == \
["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
assert find_itinerary([["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]) == ["JFK", "NRT", "JFK", "KUL"]
print("itinerary: ok")
Variant: de Bruijn sequence (cracking the safe)
Vertices are the -length strings, represented as integers in base ; the edge with symbol goes from to . The adjacency pointer is just "next symbol to try", so no edge list is stored.
def de_bruijn(k: int, n: int) -> str:
"""Shortest string containing every length-n string over digits 0..k-1 (k <= 10)."""
if n == 1:
return "".join(str(d) for d in range(k))
nodes = k ** (n - 1)
next_symbol = [0] * nodes # Hierholzer pointer: next outgoing edge to use
stack, out = [0], [] # start at "00...0"
while stack:
u = stack[-1]
if next_symbol[u] < k:
c = next_symbol[u]
next_symbol[u] += 1
stack.append((u * k + c) % nodes)
else:
out.append(stack.pop())
out.reverse() # a vertex sequence of length k^n + 1
# spell it: the first vertex in full, then the last digit of each following vertex
first = format_base(out[0], k, n - 1)
return first + "".join(str(v % k) for v in out[1:])
def format_base(x: int, k: int, width: int) -> str:
digits = []
for _ in range(width):
digits.append(str(x % k))
x //= k
return "".join(reversed(digits))
for k, n in [(2, 1), (2, 2), (2, 3), (3, 2), (2, 4), (10, 3)]:
s = de_bruijn(k, n)
assert len(s) == k ** n + n - 1
assert len({s[i:i + n] for i in range(len(s) - n + 1)}) == k ** n
assert de_bruijn(2, 3) == "0001011100"
print("de bruijn: ok")
Variant: TSP with Held–Karp
def tsp(dist: list[list[int]]) -> int:
"""Minimum cost of a cycle through all cities, starting and ending at city 0."""
n = len(dist)
INF = float("inf")
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(1, 1 << n, 2): # odd masks contain city 0
for v in range(n):
cur = dp[mask][v]
if cur == INF:
continue
for w in range(n):
if not mask >> w & 1:
nxt = mask | 1 << w
if cur + dist[v][w] < dp[nxt][w]:
dp[nxt][w] = cur + dist[v][w]
full = (1 << n) - 1
return min(dp[full][v] + dist[v][0] for v in range(1, n)) if n > 1 else 0
d = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
assert tsp(d) == 80 # 0-1-3-2-0: 10 + 25 + 30 + 15
from itertools import permutations
assert tsp(d) == min(d[0][p[0]] + sum(d[p[i]][p[i + 1]] for i in range(2)) + d[p[-1]][0]
for p in permutations([1, 2, 3]))
print("tsp: ok")
Variant: backtracking with pruning
def hamiltonian_path_backtracking(n: int, edges: list[tuple[int, int]]) -> list[int] | None:
"""Any Hamiltonian path in an undirected graph, or None. Exponential worst case."""
adj = [set() for _ in range(n)]
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
visited = [False] * n
path: list[int] = []
def remaining_connected(cur: int) -> bool:
# the unvisited vertices plus cur must be connected, or no completion exists
todo = n - len(path)
if todo == 0:
return True
seen, stack, count = {cur}, [cur], 0
while stack:
u = stack.pop()
for w in adj[u]:
if not visited[w] and w not in seen:
seen.add(w)
count += 1
stack.append(w)
return count == todo
def extend(cur: int) -> bool:
if len(path) == n:
return True
if not remaining_connected(cur):
return False
options = [w for w in adj[cur] if not visited[w]]
options.sort(key=lambda w: sum(1 for x in adj[w] if not visited[x])) # fewest exits first
for w in options:
visited[w] = True
path.append(w)
if extend(w):
return True
path.pop()
visited[w] = False
return False
for s in range(n):
visited[s] = True
path.append(s)
if extend(s):
return path
path.pop()
visited[s] = False
return None
def is_ham_path(n, edges, p):
es = {frozenset(e) for e in edges}
return p is not None and sorted(p) == list(range(n)) and all(frozenset((p[i], p[i + 1])) in es for i in range(n - 1))
petersen = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 5), (1, 6), (2, 7), (3, 8), (4, 9),
(5, 7), (7, 9), (9, 6), (6, 8), (8, 5)]
assert is_ham_path(10, petersen, hamiltonian_path_backtracking(10, petersen)) # Petersen: path yes, cycle no
star = [(0, 1), (0, 2), (0, 3)]
assert hamiltonian_path_backtracking(4, star) is None
print("backtracking: ok")
Variant: knight's tour with Warnsdorff ordering and backtracking
MOVES = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
def knights_tour(start_row: int, start_col: int, size: int = 8) -> list[list[int]] | None:
"""board[r][c] = move number (1..size*size). Warnsdorff order, iterative backtracking."""
board = [[0] * size for _ in range(size)]
def free_moves(r: int, c: int) -> list[tuple[int, int]]:
return [(r + dr, c + dc) for dr, dc in MOVES
if 0 <= r + dr < size and 0 <= c + dc < size and board[r + dr][c + dc] == 0]
def ordered(r: int, c: int) -> list[tuple[int, int]]:
return sorted(free_moves(r, c), key=lambda p: len(free_moves(*p))) # stable: ties keep move order
board[start_row][start_col] = 1
stack = [(start_row, start_col, ordered(start_row, start_col), 0)]
while stack:
r, c, cand, i = stack[-1]
if board[r][c] == size * size:
return board
if i == len(cand): # dead end: undo this square
board[r][c] = 0
stack.pop()
continue
stack[-1] = (r, c, cand, i + 1)
nr, nc = cand[i]
board[nr][nc] = board[r][c] + 1
stack.append((nr, nc, ordered(nr, nc), 0))
return None
def valid_tour(board, size):
pos = {board[r][c]: (r, c) for r in range(size) for c in range(size)}
if sorted(pos) != list(range(1, size * size + 1)):
return False
return all((abs(pos[k][0] - pos[k + 1][0]), abs(pos[k][1] - pos[k + 1][1])) in {(1, 2), (2, 1)}
for k in range(1, size * size))
for r in range(8):
for c in range(8):
assert valid_tour(knights_tour(r, c), 8)
assert knights_tour(0, 0, 4) is None # no tour exists on 4x4
assert valid_tour(knights_tour(0, 0, 5), 5)
print("knight's tour: ok")
Real-world uses
- Genome assembly. Short-read DNA assemblers (Velvet, SPAdes, and the de Bruijn graph approach introduced by Pevzner, Tang and Waterman in 2001) chop reads into -mers, build a de Bruijn graph on -mers, and reconstruct the genome as an Euler path — turning what looked like a Hamiltonian problem on reads (the "overlap graph") into a linear-time Euler problem on -mers. Real data needs error correction and repeat resolution on top, but the core reframing is exactly this lesson's edges-versus-vertices contrast.
- Testing state machines and protocols. To exercise every transition of a finite-state machine (a network protocol, a UI flow, a parser) at least once in a single test sequence, find a Chinese postman tour of the transition graph. This is a classical technique in conformance testing of communication protocols (the "transition tour" method).
- Route planning for street coverage. Snow ploughs, street sweepers, garbage trucks, meter readers and mail carriers need routes covering every street: arc-routing problems built on Chinese postman and its capacitated relatives. Real deployments add turn penalties, one-way streets (making the mixed version NP-hard) and multiple vehicles, solved with heuristics.
- De Bruijn sequences in hardware and sensing. Rotary encoders and structured-light 3D scanners project or print de Bruijn patterns so that any window of consecutive symbols identifies a unique position; linear-feedback shift registers generate closely related maximal sequences used in spread-spectrum and testing. "Cracking the safe" is the toy version.
- Drawing and CNC tool paths. Plotting a line drawing without lifting the pen is an Euler path on the drawing's graph; when impossible, the minimum number of pen lifts is (odd vertices)/2 − 1 per component — a Chinese-postman-flavoured fix. Laser cutters and plotters optimise pen-up travel with TSP heuristics.
- Logistics and the TSP. Delivery routing, drilling holes in circuit boards (a classic TSP benchmark set), telescope scheduling and genome mapping are TSP instances; production systems use heuristics and branch-and-cut (Concorde, Google OR-Tools' routing library), with the exact bitmask DP reserved for tiny subproblems such as sequencing the stops inside one route.
- Distributed systems and networks. Gossip and token-passing schemes sometimes use Hamiltonian cycles of a topology (a logical ring) so that a token visits each node once per round; finding such a ring on arbitrary topologies is hard, which is why systems impose structured overlays instead. See gossip protocols for the randomised alternative and consistent hashing for rings built by hashing rather than by search.
Pitfalls & edge cases
- Wrong start vertex. Starting an undirected Euler path at an even vertex when two odd ones exist yields a sequence of the right length that is not a valid trail; no cheap check notices. Always start at an odd (or surplus) vertex.
- No connectivity check. Degrees can be perfect while the edges sit in two components. The cheapest check is the output length: vertices or bust.
- Isolated vertices. They do not break Euler conditions, but a naive "graph is connected" BFS that includes them rejects valid inputs, and choosing one as the start returns a single-vertex path.
- Undirected edges used twice. Each undirected edge sits in two adjacency lists; without a used-flag by edge id, the algorithm walks it back and forth. Removing from a Python
listby value is and turns the algorithm quadratic. - Rescanning adjacency lists. Without a persistent per-vertex pointer, skipping used edges costs each visit; on a star with self-loop-like multi-edges that is .
- Recursive Hierholzer depth. Depth up to . Use the iterative form.
- Self-loops and multi-edges. Both are legal in Euler problems (a self-loop adds 2 to the degree of its vertex in undirected graphs). The edge-id approach handles them; adjacency sets do not.
- Forgetting to reverse the output. The pop order is the path backwards. For undirected circuits the reversed and unreversed sequences are both valid, which hides the bug until a directed test.
- Fixed endpoints. "Start at 1 and end at " requires checking that the surplus vertex is exactly 1 and the deficit vertex exactly (Teleporters Path), and for circuits that vertex 1 has nonzero degree (Mail Delivery).
- Bitmask DP memory.
long[1 << 20][20]is 160 MB. Useintwith modular arithmetic, skip masks that cannot occur (without vertex 0, or containing the end early), or iterate over vertices by fixing the start. - Bitmask DP order. Processing masks in increasing numeric order guarantees subsets come first. Iterating by popcount also works; iterating in any other order does not.
- Hamiltonian in Python at . states with inner loops is minutes in CPython. Use bit tricks (iterate only set bits of a precomputed adjacency mask), NumPy, or a compiled language.
- Knight's tour tie-breaking. Pure Warnsdorff can fail; keep a backtracking fallback, or randomise ties and restart.
Variations
- Euler path with constraints on order. Lexicographically smallest (sort adjacency), "must use edge first" (start there and check), or "smallest number of trails covering all edges" — in a connected undirected graph with odd vertices, exactly trails, found by adding a virtual vertex joined to every odd vertex and splitting its Euler circuit.
- Orienting edges for balance. Codeforces "One-Way Reform" asks to orient edges so that as many vertices as possible have in = out: pair odd vertices with a virtual vertex, take an Euler circuit, and orient along it. Every even-degree vertex becomes balanced.
- Mixed graphs. Euler circuits in graphs with both directed and undirected edges reduce to a max-flow feasibility problem (orient undirected edges so every vertex balances); see network flow.
- Counting Euler circuits. Directed: the BEST theorem gives an exact formula via the matrix-tree theorem, polynomial time. Undirected: #P-complete (Brightwell and Winkler, 2005).
- Hamiltonian cycle vs path. A path query reduces to a cycle query by adding a universal vertex; a cycle query is the path DP plus a closing edge back to the start.
- TSP variants. Metric TSP has a 1.5-approximation (Christofides 1976; slightly improved in 2020 by Karlin, Klein and Oveis Gharan), Euclidean TSP has a PTAS (Arora, Mitchell), and general TSP has no constant-factor approximation unless P = NP.
- Shortest path visiting all nodes (revisits allowed). LeetCode 847 is BFS over (mask, vertex) states — the same state space as the DP, explored with unit-cost BFS.
- Gray codes. A Hamiltonian cycle on the hypercube ; the reflected binary code constructs one directly, an example where structure makes a Hamiltonian problem trivial.
- Hamiltonian paths in special classes. Tournaments always have one (insertion); DAGs have one iff the topological order is unique (check consecutive edges, topological sort); grid graphs have parity-based rules.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Reconstruct Itinerary (LeetCode 332) — Use every ticket once starting from a fixed airport, lexicographically smallest. Teaches Hierholzer with sorted adjacency and why greedy walking alone fails.
Hint
Reverse-sort each adjacency list so pop() gives the smallest; push until stuck, pop into the answer, reverse at the end.
Solution
The find_itinerary variant above is the full solution: for sorting, for the walk.
2. Mail Delivery (CSES 1691) — Find a route that starts and ends at the post office and uses every street exactly once. Teaches the undirected Euler circuit with a fixed start and the connectivity length check.
Hint
All degrees even, start at 1, run Hierholzer with edge ids, check the length is .
Solution
def mail_delivery(n: int, streets: list[tuple[int, int]]) -> list[int] | None:
adj = [[] for _ in range(n + 1)]
for i, (a, b) in enumerate(streets):
adj[a].append((b, i))
adj[b].append((a, i))
if any(len(adj[v]) % 2 for v in range(1, n + 1)):
return None
used, ptr = [False] * len(streets), [0] * (n + 1)
stack, path = [1], []
while stack:
u = stack[-1]
while ptr[u] < len(adj[u]) and used[adj[u][ptr[u]][1]]:
ptr[u] += 1
if ptr[u] == len(adj[u]):
path.append(stack.pop())
else:
v, i = adj[u][ptr[u]]
used[i] = True
stack.append(v)
return path[::-1] if len(path) == len(streets) + 1 else None
route = mail_delivery(6, [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 5), (3, 6), (4, 5)])
assert route is not None and route[0] == route[-1] == 1 and len(route) == 9
assert mail_delivery(3, [(1, 2), (2, 3)]) is None # odd degrees
assert mail_delivery(6, [(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)]) is None # disconnected
print("mail delivery ok")
.
3. Teleporters Path (CSES 1693) — Use every one-way teleporter exactly once, going from level 1 to level . Teaches the directed Euler path with fixed endpoints.
Hint
Require out − in = 1 at vertex 1, in − out = 1 at , balance elsewhere (or, equivalently, add an edge and ask for a circuit). Start at 1; check length.
Solution
def teleporters_path(n: int, tele: list[tuple[int, int]]) -> list[int] | None:
adj = [[] for _ in range(n + 1)]
bal = [0] * (n + 1)
for a, b in tele:
adj[a].append(b)
bal[a] += 1
bal[b] -= 1
for v in range(1, n + 1):
want = 1 if v == 1 else (-1 if v == n else 0)
if n == 1:
want = 0
if bal[v] != want:
return None
ptr, stack, path = [0] * (n + 1), [1], []
while stack:
u = stack[-1]
if ptr[u] < len(adj[u]):
stack.append(adj[u][ptr[u]])
ptr[u] += 1
else:
path.append(stack.pop())
path.reverse()
return path if len(path) == len(tele) + 1 and path[-1] == n else None
assert teleporters_path(5, [(1, 2), (1, 3), (2, 4), (2, 5), (3, 1), (4, 2)]) == [1, 3, 1, 2, 4, 2, 5]
assert teleporters_path(3, [(1, 2), (1, 3)]) is None
print("teleporters path ok")
.
4. Valid Arrangement of Pairs (LeetCode 2097) — Order pairs so each pair's end equals the next pair's start. Teaches recognising a directed Euler path on arbitrary labels (hash-map adjacency).
Hint
Values are vertices, pairs are edges. Start at the value with out − in = 1 if any, else any start value.
5. De Bruijn Sequence (CSES 1692) — Shortest bit string containing every length- bit string. Teaches the de Bruijn construction.
Hint
Vertices are -bit integers; edge with bit goes to . Iterative Hierholzer; spell the result.
6. Cracking the Safe (LeetCode 753) — Shortest key sequence guaranteed to open an -digit lock over digits. Teaches the general- de Bruijn sequence.
Hint
The de_bruijn(k, n) variant above. Watch the case.
7. Tanya and Password (Codeforces 508D) — Recover a string from all of its length-3 substrings, given in arbitrary order. Teaches the genome-assembly reframing on a small scale.
Hint
Two-character vertices, one edge per substring. Directed Euler path; check balance and that the path uses all edges.
8. One-Way Reform (Codeforces 723E) — Orient every road to maximise the number of cities with equal in- and out-degree. Teaches the virtual-vertex trick.
Hint
The answer is the number of even-degree vertices. Connect every odd vertex to a new vertex, take an Euler circuit of each component, orient edges along it, and drop the virtual edges.
9. Johnny and Megan's Necklace (Codeforces 1361C) — Join pearl halves into one necklace maximising the beauty determined by the lowest set bit of XORs. Teaches binary search on the answer with an Euler-circuit feasibility check.
Hint
For a candidate beauty , colours modulo become vertices and pearls become edges; a necklace exists iff that multigraph has an Euler circuit. Try from 20 down.
10. Hamiltonian Flights (CSES 1690) — Count routes from city 1 to city visiting each city exactly once, with . Teaches the bitmask DP and its memory/time tuning.
Hint
The canonical counting DP above. Skip masks without city 1 and masks containing city unless full; in C++ iterate predecessors to keep the inner loop tight.
11. Shortest Path Visiting All Nodes (LeetCode 847) — Shortest walk visiting every node, revisits allowed, . Teaches BFS over (mask, vertex) states.
Hint
Multi-source BFS starting from every (bit , ). The first state with a full mask gives the answer.
Solution
from collections import deque
def shortest_path_length(graph: list[list[int]]) -> int:
n = len(graph)
full = (1 << n) - 1
dist = [[-1] * n for _ in range(1 << n)]
q = deque()
for v in range(n):
dist[1 << v][v] = 0
q.append((1 << v, v))
while q:
mask, v = q.popleft()
if mask == full:
return dist[mask][v]
for w in graph[v]:
nm = mask | 1 << w
if dist[nm][w] == -1:
dist[nm][w] = dist[mask][v] + 1
q.append((nm, w))
return 0
assert shortest_path_length([[1, 2, 3], [0], [0], [0]]) == 4
assert shortest_path_length([[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]]) == 4
assert shortest_path_length([[]]) == 0
print("shortest path visiting all nodes ok")
time worst case, memory.
12. Unique Paths III (LeetCode 980) — Count grid walks from start to end that step on every empty cell exactly once. Teaches Hamiltonian-path backtracking on a grid.
Hint
DFS with a counter of remaining empty cells; succeed only when you reach the end with the counter at zero. At most 20 cells keeps it fast.
13. Find the Shortest Superstring (LeetCode 943) — Shortest string containing every given word, up to 12 words. Teaches TSP with path reconstruction on an overlap graph — the Hamiltonian counterpart of de Bruijn.
Hint
Weight by the length added when follows (word length minus overlap). Held–Karp over (mask, last), keep parent pointers, rebuild.
14. Knight's Tour (CSES 1689) — Given a starting square, output a full knight's tour of an board. Teaches Warnsdorff's rule with a backtracking safety net.
Hint
Order candidate moves by the number of onward free squares; backtrack on a dead end. The knight's tour variant above solves every start square quickly.
Common mistakes & interview follow-ups
"Edges or vertices?" The first thing to say. Every edge once → Euler, linear. Every vertex once → Hamiltonian, NP-complete; ask about .
"Why does Hierholzer's greedy walk not get stuck?" It does get stuck, but only at the start vertex of the current loop (even degrees). It then backs up and explores loops from earlier vertices, splicing them in via the pop order.
"What if no Euler path exists — what is the minimum to add?" Undirected connected: add edges for a path, for a circuit (or duplicate shortest paths, the Chinese postman, when edges have lengths). Directed: new edges for a circuit (if weakly connected).
"Can you count Euler circuits?" Directed: BEST theorem, polynomial. Undirected: #P-complete.
"TSP with ? With ?" : Held–Karp DP, ~ steps. : no exact polynomial algorithm; use nearest-neighbour + 2-opt / Lin–Kernighan, or Christofides for a 1.5-approximation on metric instances; branch-and-cut if optimality is required and time is available.
"Hamiltonian path in a DAG?" Linear: it exists iff consecutive vertices of a topological order are all joined by edges (the order is then unique).
"Is a Hamiltonian cycle in a grid graph easy?" Bipartite parity: a grid with an odd number of cells has no Hamiltonian cycle. Rectangular grids with an even number of cells and both sides at least 2 do have one. General grid graphs (with holes) are NP-complete (Itai, Papadimitriou and Szwarcfiter, 1982).
Common mistakes interviewers watch for: wrong start vertex; forgetting to reverse; using adjacency sets (kills multi-edges); recursing deep; Hamiltonian DP with masks iterated in the wrong order; claiming a polynomial Hamiltonian algorithm.
Quick quiz
1. An undirected connected graph has degrees . Euler path, circuit, or neither? Where must it start?
Answer
Exactly two odd vertices (the two with degree 3): an Euler path, not a circuit, starting at one odd vertex and ending at the other.
2. In a directed graph, vertex has out − in = 2 and all other imbalances are 0 or −1. Euler path?
Answer
No. Every vertex must have , with at most one and one .
3. How long is a de Bruijn sequence for 4-digit decimal PINs, written linearly?
Answer
digits, versus for typing all codes separately.
4. How many states does the Hamiltonian DP have for , and roughly how many transitions?
Answer
states; up to transitions each, about — instant in C++, a few seconds in CPython.
5. Why does Hierholzer need a persistent per-vertex pointer rather than scanning the adjacency list each time?
Answer
A vertex can be on top of the stack many times (once per loop through it). Rescanning from the beginning, past edges already used, costs each time and can make the total quadratic; the pointer makes total scanning .
Further reading / sources
- L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Petropolitanae 8, 1741 (presented 1736) — the Königsberg bridges.
- C. Hierholzer and C. Wiener, "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen 6, 1873.
- cp-algorithms: Finding the Eulerian path in O(M).
- R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, 1972 (Hamiltonian circuit NP-complete).
- R. Bellman, "Dynamic programming treatment of the travelling salesman problem", JACM 9(1), 1962; M. Held and R. M. Karp, "A dynamic programming approach to sequencing problems", SIAM J. Applied Math. 10(1), 1962.
- G. A. Dirac, "Some theorems on abstract graphs", Proc. London Math. Soc. 1952; O. Ore, "Note on Hamilton circuits", American Mathematical Monthly 67(1), 1960.
- J. Edmonds and E. L. Johnson, "Matching, Euler tours and the Chinese postman", Mathematical Programming 5, 1973.
- P. A. Pevzner, H. Tang and M. S. Waterman, "An Eulerian path approach to DNA fragment assembly", PNAS 98(17), 2001.
- A. Björklund, "Determinant sums for undirected Hamiltonicity", FOCS 2010.
- D. Squirrel and P. Cull, "A Warnsdorff-rule algorithm for knight's tours on square chessboards", 1996 (Oregon State University technical report).
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 19 "Paths and circuits" (Euler and Hamiltonian paths, de Bruijn, knight's tours).
- CLRS, Introduction to Algorithms, 4th ed., problem 20-3 "Euler tour" and chapter 34 "NP-Completeness" (Hamiltonian cycle reduction).
Previous lesson: Connectivity: Bridges, Articulation Points, SCCs & Condensation · Next lesson: Bipartite Graphs, Matching & the Hungarian Algorithm
Related: Graphs overview · DFS in Depth · Topological Sort & DAG DP · Network Flow · Dynamic Programming · Backtracking & Recursion · Bit Manipulation · Course home