Euler paths and cycles with Hierholzer in Python

Why this matters

A delivery driver has to drive down every street in a neighbourhood once, and end up back at the depot if possible. A printer plotter has to draw a shape without lifting the pen and without drawing a line twice. A program that reads a graph of connections has to visit each connection exactly once. All three ask the same question: is there a walk that uses every edge once, and if there is, what is it?

This lesson gives you the test that answers the first part, and an algorithm that builds the walk for the second part. The algorithm is called Hierholzer's algorithm. It is a short loop with a stack, and it runs in time proportional to the number of vertices plus the number of edges. You will write it in Python, check it on a small graph by hand, and see the mistakes that usually break it.

The depth-first search lesson uses the same stack idea. The topological sort lesson works on directed graphs with no cycles. This lesson is about walks that use every edge, which is a different question.

Words used in this lesson

A vertex is a point in a graph, and an edge is a line between two vertices. A walk is a list of vertices where each neighbour pair is joined by an edge, and the walk may repeat vertices. A trail is a walk that never uses the same edge twice.

An Euler path is a trail that uses every edge of the graph exactly once. An Euler cycle is an Euler path that starts and ends at the same vertex. The name comes from Leonhard Euler, who studied a puzzle about seven bridges in the town of Königsberg in 1736 and showed that the puzzle has no solution.

The degree of a vertex is the number of edge ends touching it. In an undirected graph, where edges have no arrows, each edge adds one to the degree of each of its two ends. A vertex with an odd degree is an odd vertex. A self-loop is an edge from a vertex back to itself, and it adds two to that vertex's degree, one for each end.

In a directed graph, edges have arrows. The out-degree of a vertex is the number of arrows leaving it, and the in-degree is the number of arrows entering it. The balance of a vertex here means out-degree minus in-degree.

The idea: walk until you are stuck

Take a concrete picture first. Draw a house: a square with a triangular roof on top. The square has four corners, which we will number 0 at bottom left, 1 at bottom right, 2 at top right, and 3 at top left. The roof point is 4. The edges are 0 to 1, 1 to 2, 2 to 3, 3 to 0, then the two roof lines 2 to 4 and 3 to 4.

Try to draw the house without lifting your pen and without going over a line twice. Most people find a way after a few tries, and the first attempts show the rule. Start at a corner where three lines meet, not at one where only two meet. If you start at a corner with only two lines, you tend to end up stuck in the wrong place.

The rule that explains this is about degrees. For an undirected graph:

• A route that uses every edge once and starts and ends at the same vertex (an Euler cycle) exists only if every vertex has an even degree.
• A route that uses every edge once and starts and ends at different vertices (an Euler path) exists only if exactly two vertices have an odd degree. The route must start at one of them and end at the other.
• If there are more than two odd vertices, no route exists.

These are necessary conditions. There is one more requirement: the graph must be connected, which means that every vertex with at least one edge can be reached from every other such vertex. A graph with two separate triangles has all even degrees, but a single walk cannot cover both triangles, because it would have to jump between them.

Here is the house checked with code. Each edge is a tuple of two vertex numbers, such as (0, 1). A tuple is a fixed group of values written in parentheses. The degrees function adds one to each end of each edge.

The output is:

degrees: [2, 2, 3, 3, 2]
odd vertices: [2, 3]

Two vertices have an odd degree, 2 and 3. So an Euler path exists, and it must start at 2 or 3 and end at the other one. The house can be drawn, but not as a closed loop, because a cycle would need every degree to be even.

The line [v for v in range(n) if deg[v] % 2 == 1] is a list comprehension. It builds a new list by looping over range(n) and keeping only the values that pass the test after if. % gives the remainder after division, so deg[v] % 2 == 1 is true for odd numbers.

Building the route with a stack

Knowing that a route exists is only half the job. The second half is to build it. Hierholzer's algorithm does this with a stack, which is a pile where you add and remove items only at the top. The name comes from Carl Hierholzer, a German mathematician who described the method in the 1870s.

In Python, a plain list is a stack. stack.append(x) puts x on the top. stack.pop() removes the top item and returns it. stack[-1] looks at the top without removing it. The right end of the list is the top of the stack.

The idea has three parts.

1. Start at a vertex that is allowed to be a start (the odd vertex, or any vertex when every degree is even). Put it on the stack.
2. Look at the vertex on top of the stack. If it has an unused edge, take that edge, mark it used, and push the vertex at its other end. Keep doing this. You are walking forward.
3. If the top vertex has no unused edges, pop it and add it to a list called route. You are stuck, so this vertex is the end of the part of the walk you have built so far.

When the stack is empty, the list route holds the vertices in reverse order. Reverse it with route.reverse(), and you have the Euler route.

Reversing works for this reason. The first walk you make ends at a stuck vertex. Vertices are popped in the order you got stuck, which is the end of the route first. Reversing the list puts the start first. There is one more detail. If the vertex below the one you just popped still has unused edges, the walk continues from it. That new walk forms a loop that returns to the same vertex. When it is popped and reversed, the loop lands in the middle of the first walk, which is exactly where it belongs.

The pointer for each vertex matters for speed. We keep, for each vertex, the index of the next edge in its list that we have not looked at yet. Once we pass an edge, we never scan it again. This keeps the total work at about one visit per edge.

The undirected version in Python

Each edge is stored in two lists, one for each end. Each entry remembers the edge number, so that when we use an edge from one end, the other end's entry is also marked used. This is the detail that most beginners miss, and it is covered in the mistakes section.

def undirected_euler(n, edges, start):
    # adj[v] holds (neighbour, edge id) for every edge that touches v.
    adj = [[] for _ in range(n)]
    for edge_id, (a, b) in enumerate(edges):
        adj[a].append((b, edge_id))
        adj[b].append((a, edge_id))
 
    used = [False] * len(edges)
    next_idx = [0] * n
    stack = [start]
    route = []
    while stack:
        v = stack[-1]
        lst = adj[v]
        # Skip edges that were already used from the other end.
        while next_idx[v] < len(lst) and used[lst[next_idx[v]][1]]:
            next_idx[v] += 1
        if next_idx[v] < len(lst):
            to, edge_id = lst[next_idx[v]]
            next_idx[v] += 1
            used[edge_id] = True
            stack.append(to)
        else:
            route.append(stack.pop())
    route.reverse()
    return route

A few details in this code are worth reading slowly. enumerate(edges) gives the position and the item together, so edge_id is the number of the edge. to, edge_id = lst[...] unpacks a tuple into two names in one line. The while loop with next_idx[v] += 1 skips edges that were already used from the other end. The line next_idx[v] += 1 after the if moves the pointer past the edge we are about to use, so we never revisit it.

The function does not check the degree rules. It only builds a walk. The caller must check the degrees and connectivity first, or check the result afterwards.

Dry run on a small graph

A dry run means working through the algorithm by hand, one step at a time, and writing down the state after each step. It is how you find out whether you understand the method. Here is a small graph: a triangle 0, 1, 2 with a tail 2 to 3 to 4. The edges are numbered 0 to 4 in the order listed: edge 0 is 0-1, edge 1 is 1-2, edge 2 is 2-0, edge 3 is 2-3, and edge 4 is 3-4.

The degrees are 2 for vertex 0, 2 for vertex 1, 3 for vertex 2, 2 for vertex 3, and 1 for vertex 4. Vertices 2 and 4 are odd, so an Euler path must start at 2 or 4. We start at 2.

The table below was produced by running the same loop with a print statement after each step. The stack is shown from bottom to top, so the last item in each list is the top.

After step 5 the walk is stuck at 4, which is the second odd vertex, so step 6 pops it. From then on every vertex on the stack has no unused edges left, so each pop simply takes the top of the stack. No loop had to be spliced in.

Reverse the route [4, 3, 2, 0, 1, 2] and you get [2, 1, 0, 2, 3, 4]. Check the walk: 2 to 1 uses edge 1, 1 to 0 uses edge 0, 0 to 2 uses edge 2, 2 to 3 uses edge 3, and 3 to 4 uses edge 4. All five edges appear once. The route has six vertices, which is the number of edges plus one, as it must be for a walk over five edges.

The house from vertex 2 shows the same pattern with a different walk. The first walk is 2, 1, 0, 3, 2, 4, 3, and it gets stuck at 3, the other odd vertex. The pops come out as 3, 4, 2, 3, 0, 1, 2, and reversing them gives the route [2, 1, 0, 3, 2, 4, 3]. The walk visits vertex 2 twice, which is allowed, because each visit uses different edges.

Example two: directed graphs and lexical order

Directed graphs have a different degree rule, because each edge contributes to the out-degree of one vertex and the in-degree of another.

For a directed graph, an Euler path exists when the balances match one of these patterns, plus connectivity:

• Every vertex has balance 0. Then an Euler cycle exists, and it can start at any vertex that has an edge.
• Exactly one vertex has balance +1, which is where the route starts, and exactly one vertex has balance -1, where the route ends. All others have balance 0.

A common real problem uses this form. You have a list of tickets, each ticket is a pair of airports from and to, and you must use every ticket once in a single trip starting at a given airport. When several routes are possible, the answer must be the one that is smallest in dictionary order, which means alphabetical order for words. This is a well known interview question called Reconstruct Itinerary.

Take five tickets: JFK to SFO, JFK to ATL, SFO to ATL, ATL to JFK, and ATL to SFO. Start at JFK. Count the balances: JFK has out-degree 2 and in-degree 1, so balance +1. ATL has out-degree 2 and in-degree 2, so 0. SFO has out-degree 1 and in-degree 2, so -1. The route must start at JFK and end at SFO, which is consistent.

For the dictionary order, each airport keeps its outgoing destinations in a heap. A heap is a list kept in an order that makes the smallest item quick to take out. The standard library module heapq works on a normal list. heapq.heappush(list, item) adds an item, and heapq.heappop(list) removes and returns the smallest one. When the walk is at an airport, it takes the smallest destination available.

Running it prints:

['JFK', 'ATL', 'JFK', 'SFO', 'ATL', 'SFO']

This uses all five tickets and visits six airports, which is the ticket count plus one. The list is shown with quotes because print shows the Python form of a list, and each string is written with quotes around it.

defaultdict(list) is a dictionary that creates an empty list the first time you ask for a missing key. out.get(v) looks up a key without creating it. It returns None when the key is missing, and None counts as false in an if test. So if options: is true only when the airport has at least one outgoing ticket left.

The check before the return is the safeguard. If the graph is not connected, or the balance rule failed, the walk stops early and the route is too short. Returning None in that case is the signal that no route exists. When you call the function on tickets that form two separate groups, such as [("A", "B"), ("B", "A"), ("C", "D"), ("D", "C")] started at A, the result is None.

Dry run of the directed version

Take three tickets, A to C, A to B, and B to A, and start at A. A has out-degree 2 and in-degree 1, so balance +1. B has balance 0. C has balance -1. The route starts at A and ends at C.

Reverse the route to get [A, B, A, C]. Look at the choice in step 1. At A, the options were B and C. The algorithm took B, because B is smaller. That choice makes the route visit B before C. Taking C first would have ended the walk at C early, with two tickets unused.

Example three: parallel edges and self-loops

The third case is about graphs with an edge that appears twice, or an edge from a vertex to itself. These are common in real data, for example two roads between the same pair of towns. They are harder because the degree and the bookkeeping need care.

Take a graph with 4 vertices and these edges: two parallel edges between 0 and 1, a self-loop on 1, and a triangle 1-2-3. Degree counts each end of each edge, so the self-loop adds 2 to vertex 1. The undirected_euler function stores the self-loop twice in the list for vertex 1, once for each end, and the edge id keeps the two uses apart.

edges = [(0, 1), (0, 1), (1, 1), (1, 2), (2, 3), (3, 1)]
deg = degrees(4, edges)
print("multi degrees:", deg)
route = undirected_euler(4, edges, 0)
print("multi route from 0:", route, "length", len(route))

The output is:

multi degrees: [2, 6, 2, 2]
multi route from 0: [0, 1, 1, 2, 3, 1, 0] length 7

Vertex 1 has degree 6: two from the parallel edges, two from the self-loop, one from edge 1-2, and one from edge 3-1. All four degrees are even, so an Euler cycle exists, and the route starts and ends at 0. The route has seven numbers for six edges, which matches the rule. The walk uses 0-1, 1-1 (the self-loop), 1-2, 2-3, 3-1, and 1-0 in that order. The edge numbers keep the two parallel edges between 0 and 1 apart, so the route uses each one once.

Common mistakes

Forgetting that the edge is shared by both ends. An undirected edge is stored in two lists. If you mark it used only in the list of the vertex you walked from, the walk can cross the same edge again from the other end. The fix is to store the edge number with each entry and mark that number. A version that marks each pair of vertices as used, instead of each edge, fails on parallel edges. On a graph with two parallel edges, it uses one edge when the graph has two. A short check that counts the pairs it marked prints this:

pair-flag walk uses 1 edge(s), graph has 2

Starting at the wrong vertex. On the house graph, vertex 0 has an even degree. Python does not raise an error when you start there. The function still returns a list of seven numbers, which looks like a correct route:

route from 0: [0, 1, 2, 3, 4, 2, 0] length 7

But the pair 2 and 0 is not an edge in the house, so the route is invalid. The degree rule says the start must be one of the odd vertices, and the length check alone cannot catch the mistake. A route check that tests each consecutive pair against the edge list is the only full safeguard. Printed as a check, the result is False for this route.

Skipping the connectivity check. Two separate triangles have all even degrees, so the degree rule says a cycle exists. But the walk from vertex 0 only covers the first triangle:

two triangles route from 0: [0, 1, 2, 0]

The route has four numbers, not the seven that six edges would need. Comparing the route length with the edge count finds this case.

Changing a list while looping over it. In Python, removing items from a list while a for loop walks over that same list does not raise an error. It skips items instead. This small example removes every odd number from [1, 3, 5]:

items = [1, 3, 5]
for x in items:
    if x % 2 == 1:
        items.remove(x)
print(items)

The output is [3]. After 1 is removed, the loop moves to index 1, which now holds 5, so 3 is skipped and never checked. The algorithm avoids this problem by keeping a pointer per vertex and never removing from the lists. If you change the code to remove used edges from the lists directly, loop over a copy, such as for x in items[:], or build a new list.

Dictionaries are stricter. Removing a key while looping over the dictionary raises an error:

RuntimeError: dictionary changed size during iteration

Missing key in a plain dictionary. A vertex with no outgoing tickets has no entry in a plain dictionary. Asking for it with [] raises an error:

plain = {"A": ["B"]}
print(plain["B"])

KeyError: 'B'

Use out.get(v) for a lookup that may be missing, or a defaultdict(list) that creates an empty list for a new key, as the itinerary function does.

Forgetting to reverse the route. The list route is built in the order vertices are popped, which is the reverse of the walk. Skipping route.reverse() gives a list that looks like a route but is wrong. For the three-ticket example, the list before reversing is:

['C', 'A', 'B', 'A']

That list uses the step from C to A, but the tickets contain no ticket from C to A. The arrows are A to C, A to B and B to A. Reversing the list gives ['A', 'B', 'A', 'C'], which uses only real arrows.

Practice

Exercise 1. An undirected graph has the edges 0-1, 1-2, 2-3, 3-4, 4-0, and 1-3. Which vertices have odd degree? Does an Euler path exist, and if so, where must it start and end?

Show the answer

Vertex degrees are 0: 2, 1: 3, 2: 2, 3: 3, 4: 2. The odd vertices are 1 and 3. An Euler path exists, because the graph is connected and exactly two vertices are odd. It must start at 1 and end at 3, or start at 3 and end at 1. The function undirected_euler(5, edges, 1) returns [1, 0, 4, 3, 2, 1, 3], which has seven numbers for six edges.

Exercise 2. A directed graph has the arrows A to B, B to C, C to A, and C to D. Does an Euler path exist? If so, where does it start and where does it end?

Show the answer

Balances: A has out 1 and in 1, so 0. B has 0. C has out 2 and in 1, so +1. D has in 1 and out 0, so -1. The rule for one start and one end is met, so an Euler path exists. It starts at C and ends at D. The route is C, A, B, C, D. Calling itinerary([("A", "B"), ("B", "C"), ("C", "A"), ("C", "D")], "C") returns ['C', 'A', 'B', 'C', 'D'].

Exercise 3. The complete graph on four vertices has an edge between every pair of vertices, which is 6 edges. Can it be walked with an Euler path?

Show the answer

No. Each vertex touches 3 edges, so every vertex has an odd degree. Calling degrees(4, [(a, b) for a in range(4) for b in range(a + 1, 4)]) gives [3, 3, 3, 3]. Four odd vertices is more than two, so neither an Euler path nor an Euler cycle exists.

Exercise 4. Take the tickets ("A", "C"), ("A", "B"), and ("B", "A"), and start at A. Trace the stack by hand. What is the route?

Show the answer

The route is ['A', 'B', 'A', 'C']. The trace is in the directed dry run section. At A the smaller option B is taken first, then the walk returns to A and takes C, which ends the walk at C.

Exercise 5. The house graph is (0, 1), (1, 2), (2, 3), (3, 0), (2, 4), (3, 4). Starting at vertex 3 instead of 2, what route does undirected_euler return? Check that every consecutive pair is an edge.

Show the answer

The function returns [3, 2, 1, 0, 3, 4, 2]. Each pair is an edge: 3-2, 2-1, 1-0, 0-3, 3-4, 4-2. All six edges are used once. Vertex 3 is one of the two odd vertices, so this start is allowed.

Summary

• An undirected graph has an Euler cycle when every vertex has an even degree, and an Euler path when exactly two vertices are odd, both connected.
• A directed graph has an Euler path when balances are all 0 for a cycle, or exactly one +1 and one -1 for a path, plus connectivity.
• Hierholzer's algorithm walks with a stack until stuck, pops vertices into a list, and reverses the list at the end.
• Store each undirected edge with its number, and mark the number used, so both ends agree.
• Start the undirected walk at an odd vertex, and check the route length and the connectivity before you trust the result.