Eulerian & Hamiltonian

Two questions that sound like near-twins and could not be further apart in difficulty:

• Eulerian - is there a walk that uses every edge exactly once? Answerable by counting degrees, and constructible in O(E).
• Hamiltonian - is there a walk that visits every vertex exactly once? NP-complete. No degree test, no polynomial algorithm, and the practical answer is exponential DP over subsets.

That asymmetry is the single most useful thing on this page. Recognising which of the two a problem is asking for tells you immediately whether you are writing 15 lines or reaching for bitmask DP.

Mnemonic

Euler eats EDGES; Hamilton hits HOMES (vertices). Both start with the same letters as what they consume. Euler is easy, Hamilton is hard - and the alphabetical order matches the difficulty order.

1. Eulerian paths and circuits

An Eulerian path (or trail, since by definition it may not repeat an edge) uses every edge of the graph exactly once. An Eulerian circuit is an Eulerian path that ends where it started.

Whether one exists is decided entirely by degree parity, with no search at all. Think about what a walk does at a vertex it passes through: it comes in on one edge and leaves on another, consuming edges two at a time. So every vertex that is not an endpoint of the walk must have an even degree. The only vertices allowed to be odd are the two ends - and if the walk is closed, even those pair up.

Undirected graph	Condition	Where you may start
Eulerian circuit	connected (over the vertices that have edges) and every degree is even	anywhere
Eulerian path	connected and exactly two vertices have odd degree	at one of the two odd vertices - and you will finish at the other
Neither	four or more odd-degree vertices, or the edges span more than one component	n/a

There can never be exactly one odd-degree vertex - the handshake lemma (Graph Anatomy) forces the count of odd-degree vertices to be even. So the only cases are 0 odd (circuit), 2 odd (path), or 4+ odd (nothing).

The Konigsberg bridges as Euler drew them in 1736, right - the negative result that founded the field.

Directed graphs

Direction replaces "even degree" with "balanced degree" - what has to match at a pass-through vertex is that every arrival is paid for by a departure:

Directed graph	Condition
Eulerian circuit	every vertex has in_degree == out_degree, and all edges lie in one strongly connected piece
Eulerian path	exactly one vertex has out_degree - in_degree == 1 (that is the start), exactly one has in_degree - out_degree == 1 (that is the end), and every other vertex is balanced

⚠

The directed case can't start anywhere

In the directed case you cannot start anywhere. The start vertex is forced: it is the one with one more outgoing edge than incoming. Pick any other and you strand an edge. LC 332 Reconstruct Itinerary hides this by fixing the start as "JFK" - the input is guaranteed to make "JFK" that vertex, which is exactly why the problem can promise a valid itinerary always exists.

⚠

"Connected" means connected over edge-bearing vertices

"Connected" here means connected over the vertices that actually have edges. A graph with isolated vertices can still have an Eulerian circuit - those vertices simply are not part of the walk, because the walk covers every edge, not every vertex. Checking len(visited) == n instead of len(visited) == number of vertices with degree > 0 false-negatives on any input padded with lone vertices.

2. Hierholzer's algorithm

Given that a path exists, building it takes O(E) - one pass, each edge consumed once. The naive greedy "walk down unused edges until stuck" fails because you can get stuck partway with edges left over. Hierholzer's insight (1873) is that getting stuck is fine if you record the stuck vertex and back up: the stuck vertex must be the end of the walk, so it belongs last.

Walk until you are stuck, then write down where you are stuck and step back.

Every time you get stuck, the vertex you are standing on has no unused edges left, so nothing after it can exist - it is the last thing in the remaining route. Recording those dead ends in the order you hit them, then reversing at the end, splices every side-loop into exactly the right place automatically.

def euler_path_directed(graph, start):

# graph[u] = list of neighbours; this MUTATES it as edges are consumed

stack, route = [start], []

while stack:

u = stack[-1]

if graph[u]:

stack.append(graph[u].pop()) # walk down any unused edge out of u

else:

route.append(stack.pop()) # stuck: u is finished, it goes last

route.reverse()

return route

The undirected version needs one extra thing: each edge appears in two adjacency lists, so popping it from one does not consume the other copy. Give every edge an id and mark it used.

def euler_path_undirected(num_nodes, edges, start):

adj = [[] for _ in range(num_nodes)]

for eid, (u, v) in enumerate(edges):

adj[u].append((v, eid))

adj[v].append((u, eid)) # same eid on both copies

used = [False] * len(edges)

stack, route = [start], []

while stack:

u = stack[-1]

while adj[u] and used[adj[u][-1][1]]:

adj[u].pop() # drop edges the other copy already spent

if adj[u]:

v, eid = adj[u].pop()

used[eid] = True

stack.append(v)

else:

route.append(stack.pop())

route.reverse()

return route

⚠

Reversing the path at the end isn't cosmetic

Reversing at the end is not cosmetic. route is built in the order vertices finish, which is postorder - the reverse of the walk. Skip the reverse() and you get a valid Eulerian path of the reverse graph, which on an undirected input looks correct and on a directed input is silently backwards. This is the same postorder-then-reverse move as DFS-based topological sort (Cycles & Ordering).

⚠

graph[u].pop() mutates the caller's adjacency list

graph[u].pop() mutating the caller's adjacency list is load-bearing, and it is also a bug if you did not mean it. The algorithm's O(E) bound depends on an edge never being examined twice, which is what popping buys. If the caller needs the graph afterwards, deep-copy it first - not a shallow copy, or the inner lists are still shared.

Getting the lexicographically smallest itinerary (LC 332's actual ask) needs one change and no new ideas: make each adjacency list a min-heap, or sort it descending and keep popping from the end, so "any unused edge" becomes "the smallest unused edge."

3. Hamiltonian paths and cycles

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does that and returns to the start. Superficially this is the same shape of question as Eulerian, and it is nothing like it:

	Eulerian	Hamiltonian
Consumes	every edge once	every vertex once
Existence test	count degrees - O(V + E)	no known efficient test; the decision problem is NP-complete
Construction	Hierholzer, O(E)	exponential: O(2^n * n^2) bitmask DP, or branch-and-bound
Practical n	millions	about 20, occasionally 25
Weighted version	"route inspection" / Chinese postman	Travelling salesman (TSP)
Canonical problem	LC 332 Reconstruct Itinerary, LC 753 Cracking the Safe	LC 847 Shortest Path Visiting All Nodes, LC 943 Find the Shortest Superstring

The bitmask DP

With no polynomial algorithm available, the standard approach is to make the exponent as small as possible: instead of trying all n! orderings, note that what matters about a partial route is only which set of vertices it has covered and where it currently ends - not the order it covered them in. That collapses n! orderings into 2^n * n states.

def has_hamiltonian_path(num_nodes, adj):

# dp[mask][v] = "some route covering exactly `mask` ends at v"

dp = [[False] * num_nodes for _ in range(1 << num_nodes)]

for v in range(num_nodes):

dp[1 << v][v] = True # a route of one vertex

for mask in range(1 << num_nodes):

for v in range(num_nodes):

if not dp[mask][v]:

continue

for w in adj[v]:

if not mask >> w & 1: # w not covered yet

dp[mask | 1 << w][w] = True

full = (1 << num_nodes) - 1

return any(dp[full][v] for v in range(num_nodes))

Swap the booleans for costs and take a min instead of an or and the same table solves TSP. The mask mechanics - iterating set bits, testing membership, enumerating submasks - are all on the bit-manipulation core techniques page.

Mnemonic

"The order does not matter, only the set and the endpoint." That single observation is what turns O(n!) into O(2^n * n^2), and it is the tell for every bitmask DP: if you can describe a partial solution by a subset plus a tiny bit of extra state, the exponent moves from the factorial to the power of two.

⚠

n <= 20 signals bitmask DP, not coincidence

n <= 20 in the constraints is the bitmask-DP signal, and it is a hint, not a coincidence. 2^20 is about a million states; 2^25 is thirty-three million and usually still passes; 2^30 does not. If a problem says "visit every node" and n is 12 to 20, stop looking for a clever polynomial algorithm - there isn't one, and the constraint is telling you so.

In 1736 Euler was asked whether a stroll through Konigsberg could cross each of its seven bridges exactly once. His answer was no, and his reason was the first piece of graph theory ever written: he threw away the map entirely - distances, shapes, positions, all of it - and kept only which landmasses touched which bridges. Once the problem is a graph, the argument is two lines: any landmass you merely pass through needs bridges in pairs, and all four Konigsberg landmasses have an odd number, so at most two of them could be the ends of the stroll.

That is the move the whole field is built on - reducing a physical question to vertices and edges - and it is why an Eulerian walk is named after the question he answered rather than the algorithm, which arrived 137 years later.

Where to go next

• Cycles & Ordering - the postorder reversal that Hierholzer shares with DFS topological sort.
• MST & SCC - the strong-connectivity check the directed Eulerian conditions depend on.