Euler paths and cycles with Hierholzer

Why it matters

A mail carrier wants to walk down every street in a town once. A pen plotter wants to draw a picture without lifting the pen or retracing a line. A program that rebuilds a DNA sequence from short overlapping pieces wants a route that uses each overlap exactly once. All three problems ask for a walk through a graph in which every edge is used one time.

Such a walk is called an Euler path. If it ends at the vertex where it started, it is called an Euler cycle. The name honours the mathematician Leonhard Euler, who studied a puzzle about seven bridges in the town of Königsberg in 1736 and showed that no walk crossing each bridge once existed there. The question has a fast test, and the walk itself can be built with a short method named after Carl Hierholzer, who published it in 1873.

This lesson assumes you know what a graph, a vertex and an edge are, and that you have seen a stack. The representations lesson earlier in this module covers graphs, and the stacks and queues module covers stacks. Everything else is explained here.

Terms used in this lesson

A vertex is a point in a graph. An edge joins two vertices. A walk is a list of vertices in which each neighbouring pair is joined by an edge. In an Euler walk, every edge appears exactly once. A vertex may appear many times.

A graph is connected when you can get from any vertex with edges to any other vertex with edges by following edges. Lone vertices with no edges do not count against connectivity.

The degree of a vertex is the number of edges that touch it. A vertex with three edges meeting at it has degree 3.

A stack is a pile. You add to the top and remove from the top, so the last item added is the first one taken away. Programmers call this last in, first out, or LIFO.

Why degree decides the question

Look at what a walk does at a vertex in the middle of its route. It arrives along one edge and leaves along a different edge. Those two edges are used up together. Each pass through the vertex therefore uses edges in pairs, so the number of edges at that vertex must be even.

The start and the end of the walk are special. The walk leaves its start without arriving there, so one edge at the start is left over. The walk arrives at its end without leaving, so one edge at the end is left over. That gives two cases:

• If the walk starts and ends at the same vertex, no vertex has a left-over edge. Every degree is even.
• If the walk starts and ends at different vertices, exactly those two vertices have odd degree. Every other vertex has even degree.

A graph with more than two odd-degree vertices cannot be walked this way, because each extra odd vertex would need its own left-over edge.

Here is a concrete graph with five vertices, numbered 0 to 4, and five edges: 0-1, 1-2, 2-0, 0-3 and 3-4. Picture a triangle on vertices 0, 1 and 2, with a tail that runs from 0 to 3 and then to 4. The degrees are 3 for vertex 0, 2 for vertices 1, 2 and 3, and 1 for vertex 4. Vertices 0 and 4 have odd degree, so an Euler path exists. It must start at 0 or 4 and end at the other. The graph is connected. This graph is the running example for the first half of the lesson.

For graphs whose edges have no direction, the rules are these:

These rules answer whether a walk exists. They do not give the walk. For that we need the stack method.

Building the route with a stack

Start at a vertex. Walk along any edge you have not used yet, and keep walking. Each time you arrive at a vertex, push it onto the stack. At some point you will be stuck: the vertex on top of the stack has no unused edges left. When that happens, pop the top vertex off the stack and write it into a list called the route. The vertex now on top is the one you came from. If it still has an unused edge, walk from it again. Stop when the stack is empty.

The list you wrote is the route in reverse. The first vertex written is the place where the walk got stuck first, and that is the end of the route. Reading the list from its last item back to its first gives the walk in order.

Why does the first stuck point have to be the end? Every vertex other than the start and the end is passed through in pairs of edges, so the walk can always leave such a vertex again. Only the end can trap the walk, because it is the one vertex where the walk arrives without a way out. If the walk gets stuck at the start, the graph is an Euler cycle and the start is also the end.

When the walk gets stuck and you back up the stack, a vertex lower down may still have unused edges. A new walk started from that vertex must come back to it, because the edges left over still pair up at every vertex. That side loop is then placed into the route at the right point. This is why the stack is needed: it remembers where the side loops start.

Here is the walk for the triangle with a tail, started at vertex 0. The stack column shows the top on the right.

The stack is empty after step 11. The route written is 4, 3, 0, 2, 1, 0. Reverse it and you get 0, 1, 2, 0, 3, 4. Check it by hand. The walk uses the edges 0-1, 1-2, 2-0, 0-3 and 3-4, each one once, and each pair of neighbours in the walk is joined by an edge.

Notice that steps 1 to 5 went around the triangle and then down the tail, and the walk got stuck at 4, which is the odd vertex that is not the start. This matches the rule above. The walk ended where the rules said it must end.

Writing the program

The program below checks the degree rules and then builds the route. It has three parts. eulerStart applies the rules and returns the start vertex, or nothing when no Euler path exists. hierholzer builds the route with a stack. solve joins them and prints the result.

Each edge gets a number, its position in the input list. A road is stored twice, once in the list of each of its two ends, and both copies carry the same number. When the walk uses a road, it marks that number as used. That stops the walk from taking the same road back from the other end.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <optional>
#include <string>
#include <utility>
#include <vector>
 
struct Edge {
    int to;
    int id;  // position of this edge in the input list
};
 
using Graph = std::vector<std::vector<Edge>>;
 
Graph buildGraph(int n, const std::vector<std::pair<int, int>>& edges) {
    Graph adj(n);
    for (std::size_t i = 0; i < edges.size(); ++i) {
        auto [a, b] = edges[i];
        adj[a].push_back({b, static_cast<int>(i)});
        adj[b].push_back({a, static_cast<int>(i)});
    }
    return adj;
}
 
std::size_t reachableCount(const Graph& adj, int start) {
    std::vector<bool> seen(adj.size(), false);
    std::vector<int> stack{start};
    seen[start] = true;
    std::size_t count = 0;
    while (!stack.empty()) {
        int v = stack.back();
        stack.pop_back();
        ++count;
        for (const Edge& e : adj[v]) {
            if (!seen[e.to]) {
                seen[e.to] = true;
                stack.push_back(e.to);
            }
        }
    }
    return count;
}
 
std::optional<int> eulerStart(const Graph& adj) {
    std::vector<int> odd;
    int firstWithEdges = -1;
    std::size_t withEdges = 0;
    for (int v = 0; v < static_cast<int>(adj.size()); ++v) {
        if (adj[v].empty()) continue;
        ++withEdges;
        if (firstWithEdges < 0) firstWithEdges = v;
        if (adj[v].size() % 2 == 1) odd.push_back(v);
    }
    if (withEdges == 0) return std::nullopt;
    if (reachableCount(adj, firstWithEdges) != withEdges) return std::nullopt;
    if (odd.empty()) return firstWithEdges;
    if (odd.size() == 2) return odd[0];
    return std::nullopt;
}
 
std::vector<int> hierholzer(const Graph& adj, int start, std::size_t edgeCount) {
    std::vector<bool> used(edgeCount, false);
    std::vector<std::size_t> nextEdge(adj.size(), 0);
    std::vector<int> stack{start};
    std::vector<int> route;
    while (!stack.empty()) {
        int v = stack.back();
        while (nextEdge[v] < adj[v].size() && used[adj[v][nextEdge[v]].id]) ++nextEdge[v];
        if (nextEdge[v] == adj[v].size()) {
            route.push_back(v);
            stack.pop_back();
        } else {
            Edge e = adj[v][nextEdge[v]];
            used[e.id] = true;
            stack.push_back(e.to);
        }
    }
    std::reverse(route.begin(), route.end());
    return route;
}
 
void solve(const std::string& label, int n, const std::vector<std::pair<int, int>>& edges) {
    Graph adj = buildGraph(n, edges);
    auto start = eulerStart(adj);
    std::cout << label << ": ";
    if (!start) {
        std::cout << "no Euler path\n";
        return;
    }
    auto route = hierholzer(adj, *start, edges.size());
    std::cout << "start " << *start << ", route";
    for (int v : route) std::cout << ' ' << v;
    std::cout << '\n';
    if (route.size() != edges.size() + 1) std::cout << "  warning: route is too short\n";
}
 
int main() {
    solve("triangle with tail", 5, {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {3, 4}});
    solve("triangle with square", 5, {{0, 1}, {1, 2}, {2, 0}, {0, 3}, {3, 4}, {4, 0}});
    solve("star with four leaves", 5, {{0, 1}, {0, 2}, {0, 3}, {0, 4}});
    solve("two disconnected triangles", 6, {{0, 1}, {1, 2}, {2, 0}, {3, 4}, {4, 5}, {5, 3}});
}

Compile and run it with g++ -std=c++20 -Wall -o euler euler.cpp && ./euler. The output is:

triangle with tail: start 0, route 0 1 2 0 3 4
triangle with square: start 0, route 0 1 2 0 3 4 0
star with four leaves: no Euler path
two disconnected triangles: no Euler path

The triangle with a tail gives the route traced above. Adding the edge 4-0 makes every degree even, so the answer becomes an Euler cycle that ends at 0. The star has four odd leaves, so no walk exists. The two triangles are not connected to each other, so the rules fail on connectivity even though every degree is even.

The check in solve for a route of the right length is a weak test. You will see why in the mistakes section.

Directed graphs: the itinerary problem

A directed graph has one-way edges. Think of flights: a flight from Delhi to Dubai does not mean there is a flight back. In a directed graph, each edge is an arrow, and each vertex has two counts. The out-degree is the number of arrows leaving it, and the in-degree is the number of arrows arriving at it.

The rules change a little. For an Euler cycle, every vertex must have out-degree equal to in-degree. For an Euler path, one vertex may have one more outgoing arrow than incoming arrows (this is the start), one vertex may have one more incoming arrow than outgoing (this is the end), and every other vertex must balance.

A common interview version gives a list of tickets. Each ticket is a pair [from, to], and every ticket must be used exactly once. Given a starting city, the task is to return an itinerary that uses all the tickets. When more than one answer exists, return the one that is first in alphabetical order, reading city names one after another.

Take these four tickets: MUC to LHR, JFK to MUC, SFO to SJC, and LHR to SFO. Starting at JFK, the only itinerary is JFK, MUC, LHR, SFO, SJC. Each ticket is used once and each flight starts where the last one ended.

The directed version of the rules is simpler to check when you count the balance of each city. For each ticket from a to b, add 1 to the balance of a and take 1 from the balance of b. A city with balance 0 has equal in and out tickets. The start city may have balance 1. Exactly one city may have balance minus 1, which is the end. Every ticket adds 1 in one place and takes 1 away in another, so all balances add up to 0. This means that a single city with balance 1 forces exactly one city with balance minus 1.

The walk is the same stack method as before, with two changes. There are no edge numbers, because a ticket is used by moving past it in the sorted list of destinations. The destinations of each city are sorted, so the walk always takes the alphabetically first unused destination. The route is still reversed at the end.

Here is a second example that shows why the stack matters. The tickets are JFK to KUL, JFK to NRT, and NRT to JFK. The city KUL is a dead end: no ticket leaves it. Walk from JFK and take the first destination, KUL. You are stuck at KUL, so it is pushed out to the route first. Go back to JFK, take NRT, then JFK again, and finally stop at JFK with nothing left. The route written is KUL, JFK, NRT, JFK. Reversed, it is JFK, NRT, JFK, KUL. The dead end went last in the list, which is where it belongs.

Here is the full itinerary program.

#include <algorithm>
#include <iostream>
#include <map>
#include <optional>
#include <string>
#include <utility>
#include <vector>
 
using Ticket = std::pair<std::string, std::string>;
 
std::optional<std::vector<std::string>> findItinerary(const std::vector<Ticket>& tickets,
                                                      const std::string& start) {
    std::map<std::string, std::vector<std::string>> out;
    std::map<std::string, int> balance;
    for (const auto& [from, to] : tickets) {
        out[from].push_back(to);
        ++balance[from];
        --balance[to];
    }
    for (auto& [city, dests] : out) std::sort(dests.begin(), dests.end());
 
    for (const auto& [city, b] : balance) {
        if (b == 0) continue;
        if (city == start && b == 1) continue;
        if (b == -1) continue;
        return std::nullopt;
    }
 
    std::map<std::string, std::size_t> nextIdx;
    std::vector<std::string> stack{start};
    std::vector<std::string> route;
    while (!stack.empty()) {
        const std::string city = stack.back();
        const auto& dests = out[city];
        std::size_t& i = nextIdx[city];
        if (i < dests.size()) {
            stack.push_back(dests[i++]);
        } else {
            route.push_back(city);
            stack.pop_back();
        }
    }
    if (route.size() != tickets.size() + 1) return std::nullopt;
    std::reverse(route.begin(), route.end());
    return route;
}
 
void show(const std::vector<Ticket>& tickets, const std::string& start) {
    auto route = findItinerary(tickets, start);
    if (!route) {
        std::cout << "no itinerary from " << start << '\n';
        return;
    }
    for (std::size_t i = 0; i < route->size(); ++i) {
        std::cout << (i ? " " : "") << (*route)[i];
    }
    std::cout << '\n';
}
 
int main() {
    show({{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}}, "JFK");
    show({{"JFK", "KUL"}, {"JFK", "NRT"}, {"NRT", "JFK"}}, "JFK");
    show({{"A", "B"}, {"C", "D"}}, "A");
}

The output is:

JFK MUC LHR SFO SJC
JFK NRT JFK KUL
no itinerary from A

The third case has two cities with more departures than arrivals, A and C. Only the start may have that, so the balance check rejects the input.

The line const auto& dests = out[city]; holds a reference into the map. A std::map keeps its other entries in place when a new key is added, so the reference stays valid. The city variable is a copy of the top of the stack, because stack.push_back can move the stack's contents in memory, which would make a reference into the stack unsafe.

Common mistakes

Forgetting to reverse the route

If you print the route as it was written, the walk runs backwards. Remove the std::reverse line from the itinerary program and run it again. The output is:

SJC SFO LHR MUC JFK
KUL JFK NRT JFK
no itinerary from A

For an undirected graph, the reversed walk is also a valid walk, so the mistake shows up less. The triangle with a tail, written without the reverse, gives 4 3 0 2 1 0. That is a valid walk, but it starts at 4 and ends at 0. For directed tickets the reverse is essential, because the direction of each flight matters.

Starting from the wrong vertex

A path must begin at an odd-degree vertex. Vertex 1 in the triangle with a tail has even degree, so starting there is wrong. The variant below replaces return odd[0]; with return 1;, and nothing else changes. Its output is:

triangle with tail: start 1, route 1 0 3 4 2 1
triangle with square: start 0, route 0 1 2 0 3 4 0
star with four leaves: no Euler path
two disconnected triangles: no Euler path

The route 1 0 3 4 2 1 contains the step from 4 to 2. There is no edge between 4 and 2 in this graph, so the route is not a valid walk. The route has six vertices for five edges, so the length check in solve passes and prints no warning. The length check is not enough. The degree rule is what proves the start is correct, so check the degree rule first and build the route only after it passes. The eulerStart function does this.

Not marking a road as used at both ends

An undirected road appears in the list of each of its two endpoints. The used mark belongs to the road, which is why the program stores a road number. Marking vertices as used instead is a common mistake. A vertex can be entered and left many times in one walk, so a vertex mark stops the walk too early. Without any used check, the walk takes the same road back and forth, the stack grows without end, and the program eventually crashes.

Forgetting the include for std::reverse

std::reverse is declared in the <algorithm> header. A program that uses it without including that header fails to compile. This small test file uses std::reverse with only <iostream> and <vector> included:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> route{1, 2, 3};
    std::reverse(route.begin(), route.end());
    std::cout << route[0] << "\n";
}

The compiler reports:

mistakes_reverse.cpp: In function ‘int main()’:
mistakes_reverse.cpp:6:10: error: ‘reverse’ is not a member of ‘std’
    6 |     std::reverse(route.begin(), route.end());
      |          ^~~~~~~

The fix is to add #include <algorithm> at the top of the file. The message names the function and the namespace, so it is easy to find the missing header.

Practice

Exercise 1. A graph has five edges: 0-1, 1-2, 2-3, 3-0 and 1-3. Find the degree of each vertex, say whether the graph has an Euler path or an Euler cycle, and name the valid start vertices.

Show the answer

The degrees are 2 for vertex 0, 3 for vertex 1, 2 for vertex 2 and 3 for vertex 3. Vertices 1 and 3 are odd, so the graph has an Euler path and no Euler cycle. The path must start at 1 and end at 3, or start at 3 and end at 1. The program gives 1 0 3 2 1 3 when it starts at 1.

Exercise 2. Use the triangle with a tail, with edges 0-1, 1-2, 2-0, 0-3 and 3-4. Dry-run the stack method from vertex 4 instead of vertex 0. Write the route you get.

Show the answer

Starting at 4 gives the route 4 3 0 1 2 0. Check it: the walk goes 4 to 3, 3 to 0, 0 to 1, 1 to 2 and 2 to 0. These are the five edges, each used once. The walk goes round the triangle in the same direction as the lesson's walk, but it starts at 4 and ends at 0.

Exercise 3. Use the directed itinerary program on these tickets, starting from A: A to B, B to C, C to A, and A to D. Write the itinerary. Then explain which rule decided the first step.

Show the answer

The itinerary is A B C A D. The city A has two outgoing tickets, to B and to D. The walk takes B first because it comes before D alphabetically. The walk then returns to A and takes D last. The city D has no tickets leaving it, so it is written into the route first and ends up last after the reverse.

Exercise 4. A graph has four vertices of odd degree. Explain in plain words why it cannot have an Euler path.

Show the answer

Each pass through a vertex in the middle of a walk uses two edges, one in and one out, so the number of edges at that vertex is even. Only the start and the end of a walk can have an odd number of edges, because each of them has one edge left over. A path has two such ends at most. Four odd vertices would need four ends, so the walk cannot exist.

Exercise 5. Find the itinerary for these tickets, starting from JFK: JFK to AAA, AAA to JFK, JFK to BBB, and BBB to JFK. Write the answer.

Show the answer

The answer is JFK AAA JFK BBB JFK. The city JFK has two outgoing tickets, to AAA and BBB, and the walk takes AAA first. It returns to JFK, takes BBB, and returns to JFK. Every city balances, so this is an Euler cycle that starts and ends at JFK.

Summary

• An Euler path uses every edge exactly once. An Euler cycle is one that ends where it started.
• For undirected graphs, the graph must be connected. It has an Euler cycle when all degrees are even, and an Euler path when exactly two degrees are odd.
• For directed graphs, count out-degree minus in-degree. A walk needs at most one start with plus 1, at most one end with minus 1, and all other vertices at 0.
• Hierholzer's method builds the route with a stack. Walk until stuck, write the stuck vertex down, back up, and walk again. Reverse the list at the end.
• The route length check does not prove a route is valid. Check the degree rules first.
• For directed tickets, the reverse step is required, and sorting destinations gives a fixed answer when more than one exists.