Eulerian Paths and Cycles

Lesson 15 of 17 · Graphs and trees

Can a figure be drawn in one stroke, without lifting the pencil and without going over the same line twice? That is the question of whether a graph has an Eulerian path – a path that goes through every edge exactly once. The answer depends only on the degrees of the vertices, and the path itself is found by Hierholzer's algorithm.

Before you start: prerequisites – DFS.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

When does it exist?

For an undirected graph in which all the edges are in one component:

The number of vertices of odd degreeResult
0there is an Eulerian cycle (the path returns to the starting vertex) – it starts from any vertex
2there is an Eulerian path – it starts in one and ends in the other vertex of odd degree
more than 2it does not exist

Why: every time we pass through a vertex, we use one incoming and one outgoing edge, so the inner vertices of the path must have an even degree. Only the start and the end can be odd.

For a directed graph: a cycle exists if for every vertex the number of incoming edges equals the number of outgoing ones; a path exists if one vertex has one more outgoing edge (the start), one has one more incoming edge (the end), and all the others are balanced.

The famous problem of the Seven Bridges of Königsberg has no solution because all four parts of the city have an odd degree.

Hierholzer's algorithm

We start from the starting vertex and go along unused edges until we get stuck. When a vertex has no more unused edges, it goes into the result and we step back – from there we may start a new "round" that is inserted into the path. The result is obtained in reverse order. Every edge is used once, so the complexity is O(n + m).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);  // (neighbour, the index of the edge)
    vector<int> degree(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back({v, i});
        graph[v].push_back({u, i});
        degree[u]++;
        degree[v]++;
    }
    // the start: a vertex of odd degree, if there is one; otherwise any vertex with an edge
    int start = 1, oddCount = 0;
    for (int v = 1; v <= n; v++) if (degree[v] > 0) { start = v; break; }
    for (int v = 1; v <= n; v++)
        if (degree[v] % 2 == 1) {
            if (oddCount == 0) start = v;
            oddCount++;
        }
    if (oddCount != 0 && oddCount != 2) {
        cout << "DOES NOT EXIST" << endl;
        return 0;
    }
    vector<bool> used(m, false);
    vector<size_t> nextEdge(n + 1, 0);          // from which edge we continue looking through the vertex's list
    vector<int> stack = {start}, path;
    while (!stack.empty()) {
        int v = stack.back();
        while (nextEdge[v] < graph[v].size() && used[graph[v][nextEdge[v]].second]) nextEdge[v]++;
        if (nextEdge[v] == graph[v].size()) {   // there are no more edges from v
            path.push_back(v);
            stack.pop_back();
        } else {
            auto [u, id] = graph[v][nextEdge[v]];
            used[id] = true;                    // we cross the edge v-u
            stack.push_back(u);
        }
    }
    if ((int)path.size() != m + 1) {            // not all the edges are in the same component
        cout << "DOES NOT EXIST" << endl;
        return 0;
    }
    reverse(path.begin(), path.end());
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << (i + 1 < path.size() ? " " : "\n");
    return 0;
}

Example

Input

4 5
1 2
2 3
3 4
4 1
1 3

Output

1 2 3 4 1 3

The vertices 1 and 3 have an odd degree (3), so the path starts in 1 and ends in 3, and it uses each of the 5 edges exactly once.

The algorithm is written with its own stack instead of recursion, because a path can have a million edges. The array nextEdge keeps how far we have got in the list of neighbours, so that the same (already used) edges are not checked again.

Note: an older version of this lesson described Fleury's algorithm. It is easier to understand, but at every step it checks whether an edge is a bridge, so it runs in O(m²) – too slow for competitions.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

In one stroke

A figure is given as an undirected connected graph (points and lines). Print CYCLE if it can be drawn in one stroke so that it ends at the starting point, PATH if it can, but not at the starting point, and NO if it cannot.

Example 1

Input

4 5
1 2
2 3
3 4
4 1
1 3

Output

PATH

Example 2

Input

3 3
1 2
2 3
3 1

Output

CYCLE

Example 3

Input

4 3
1 2
1 3
1 4

Output

NO
Common mistakes and tips
  • The parity conditions hold only if all the edges are in one component – check that the path contains all m edges.
  • Mark every edge as used by its index, so that it is not crossed twice (once from each end).
  • For a large graph use the version with a stack, not recursion.

Check your knowledge

Open the quiz

Eulerian paths

1. When does an undirected connected graph have an Eulerian cycle?




2. A graph has 4 vertices of odd degree. Does it have an Eulerian path?




3. What is the complexity of Hierholzer's algorithm?