Euler Path & Euler Circuit

April 2026 · 25 min read

What Is an Euler Path & Euler Circuit?

In 1736, the citizens of Königsberg posed a simple question: can you walk through the city, crossing each of its seven bridges exactly once? Leonhard Euler proved that the answer is no, and in doing so invented graph theory. The problem became the foundation for what we now call Euler paths and Euler circuits.

The Königsberg Bridge Problem

Königsberg (modern-day Kaliningrad) had four landmasses connected by seven bridges. Euler modeled each landmass as a vertex and each bridge as an edge:

Every vertex (landmass) has an odd degree: A has 3 edges, B has 5, C has 3, and D has 3. Euler proved that you need at most 2 odd-degree vertices for a traversal to exist. With four odd-degree vertices, it is impossible.

Definitions

Example: A Graph with an Euler Circuit

Conditions for Existence

Before searching for an Euler path or circuit, check whether one exists. The rules differ for undirected and directed graphs.

Undirected Graphs

Directed Graphs

Comparison Table

Visual: Which Graphs Have Euler Paths?

Degree Analysis: Quick Check

Given any graph, you can determine whether an Euler path or circuit exists by counting vertex degrees. Here is the systematic procedure:

Degree Check: Visual Example

C++ Existence Check

// Check Euler path/circuit existence in an undirected graph
// Returns: 0 = neither, 1 = Euler path, 2 = Euler circuit
int checkEuler(int n, vector<vector<int>>& adj) {
    // 1. Check connectivity (BFS from first non-isolated vertex)
    int start = -1;
    vector<int> deg(n, 0);
    for (int u = 0; u < n; u++) {
        deg[u] = adj[u].size();
        if (deg[u] > 0 && start == -1) start = u;
    }
    if (start == -1) return 2; // no edges, trivially Eulerian

    vector<bool> vis(n, false);
    queue<int> q;
    q.push(start);
    vis[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!vis[v]) { vis[v] = true; q.push(v); }
        }
    }
    for (int u = 0; u < n; u++)
        if (deg[u] > 0 && !vis[u]) return 0; // not connected

    // 2. Count odd-degree vertices
    int oddCount = 0;
    for (int u = 0; u < n; u++)
        if (deg[u] % 2 != 0) oddCount++;

    if (oddCount == 0) return 2;      // Euler circuit
    if (oddCount == 2) return 1;      // Euler path
    return 0;                          // neither
}

Hierholzer's Algorithm

Hierholzer's algorithm (1873) is the standard O(V + E) method for finding an Euler path or circuit. The key insight: build sub-circuits and splice them together.

Why the Naive Approach Fails

A naive strategy — "just follow unused edges until you get stuck" — can fail badly. You might get stuck at a vertex that still has unused edges elsewhere in the graph. The visited edges form a sub-circuit, but many edges remain unvisited.

The Post-Order Trick

Instead of recording vertices as you enter them, record them as you leave them (when all their edges are exhausted). Then reverse the result. This guarantees that any sub-circuits are properly spliced into the main path.

Pseudocode

How It Works

1. Push start onto the stack.
2. Peek at the top of the stack. If the current vertex has unused edges, pick one, mark it used, and push the neighbor.
3. If the current vertex has no unused edges, pop it and add it to the circuit list (post-order).
4. Repeat until the stack is empty.
5. Reverse the circuit list to get the correct order.

Step-by-Step Visual Walkthrough

Let us trace Hierholzer's algorithm on our example graph with 6 nodes and 8 edges. All vertices have even degree, so an Euler circuit exists.

Graph edges: 0-1, 0-2, 1-2, 1-3, 2-3, 3-4, 3-5, 4-5

We will process neighbors in ascending order. The algorithm uses a stack (DFS) and a circuit list (post-order result).

Interactive Animation

Watch Hierholzer's algorithm run on the example graph. The animation colors edges as they are traversed and tracks the stack and circuit as data structure panels.

Euler Path in Directed Graphs

For directed graphs, Hierholzer's algorithm works the same way — but edge removal is simpler (each directed edge exists only once) and the existence conditions involve in-degree and out-degree.

Directed Euler Path Example

Finding the Start Vertex (Directed)

// Find start vertex for directed Euler path
int findStart(int n, vector<vector<int>>& adj) {
    vector<int> in_deg(n, 0), out_deg(n, 0);
    for (int u = 0; u < n; u++) {
        out_deg[u] = adj[u].size();
        for (int v : adj[u]) in_deg[v]++;
    }
    int start = 0;
    for (int u = 0; u < n; u++) {
        if (out_deg[u] - in_deg[u] == 1) return u; // must start here
    }
    // All balanced → circuit, start anywhere with edges
    for (int u = 0; u < n; u++)
        if (out_deg[u] > 0) return u;
    return 0;
}

C++ Implementation (Undirected)

Undirected Euler paths require careful edge tracking: when you use edge (u, v), you must also mark the reverse edge (v, u) as used. We use edge indices to handle this.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to, id;
};

vector<int> eulerPathUndirected(int n, vector<pair<int,int>>& edges) {
    vector<vector<Edge>> adj(n);
    int m = edges.size();

    // Build adjacency list with edge IDs
    for (int i = 0; i < m; i++) {
        auto [u, v] = edges[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    // Find start vertex
    int start = 0;
    vector<int> deg(n, 0);
    for (int u = 0; u < n; u++) deg[u] = adj[u].size();
    for (int u = 0; u < n; u++) {
        if (deg[u] % 2 == 1) { start = u; break; }
    }

    // Hierholzer's algorithm
    vector<bool> usedEdge(m, false);
    vector<int> idx(n, 0);   // next edge to try for each vertex
    stack<int> stk;
    vector<int> circuit;

    stk.push(start);
    while (!stk.empty()) {
        int u = stk.top();
        if (idx[u] < (int)adj[u].size()) {
            auto& e = adj[u][idx[u]];
            idx[u]++;
            if (usedEdge[e.id]) continue; // skip used edges
            usedEdge[e.id] = true;
            stk.push(e.to);
        } else {
            circuit.push_back(u);
            stk.pop();
        }
    }

    reverse(circuit.begin(), circuit.end());
    return circuit;  // size = m + 1 for circuit, m + 1 for path
}

int main() {
    int n = 6;
    vector<pair<int,int>> edges = {
        {0,1}, {0,2}, {1,2}, {1,3}, {2,3}, {3,4}, {3,5}, {4,5}
    };
    auto path = eulerPathUndirected(n, edges);

    for (int v : path) cout << v << " ";
    // Output: 0 1 2 3 4 5 3 1 0 (or similar valid Euler circuit)
    return 0;
}

Complexity Analysis

Directed Graph Implementation

Directed graphs are simpler to implement: each edge exists in only one direction, so there is no need for edge IDs or dual marking.

#include <bits/stdc++.h>
using namespace std;

vector<int> eulerPathDirected(int n, vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> in_deg(n, 0), out_deg(n, 0);

    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        out_deg[u]++;
        in_deg[v]++;
    }

    // Sort neighbors for deterministic output (optional)
    for (int u = 0; u < n; u++)
        sort(adj[u].begin(), adj[u].end());

    // Find start vertex
    int start = 0;
    for (int u = 0; u < n; u++) {
        if (out_deg[u] - in_deg[u] == 1) { start = u; break; }
        if (out_deg[u] > 0) start = u;
    }

    // Hierholzer's with index pointers
    vector<int> idx(n, 0);
    stack<int> stk;
    vector<int> circuit;

    stk.push(start);
    while (!stk.empty()) {
        int u = stk.top();
        if (idx[u] < (int)adj[u].size()) {
            stk.push(adj[u][idx[u]++]);
        } else {
            circuit.push_back(u);
            stk.pop();
        }
    }

    reverse(circuit.begin(), circuit.end());
    return circuit;
}

int main() {
    int n = 4;
    // Directed edges forming an Euler circuit
    vector<pair<int,int>> edges = {
        {0,1}, {1,2}, {2,3}, {3,0}, {0,2}, {2,0}
    };
    auto path = eulerPathDirected(n, edges);

    for (int v : path) cout << v << " ";
    // Output: 0 1 2 0 2 3 0 (or similar valid Euler circuit)
    return 0;
}

Applications

Euler paths and circuits appear in many practical and theoretical contexts:

Interview & CP Problems

Summary

Key Takeaways

• Euler path visits every edge exactly once; Hamiltonian path visits every vertex exactly once.
• Existence can be checked in O(V + E) by counting degrees and verifying connectivity.
• Hierholzer's algorithm finds the path/circuit in O(V + E) using the post-order trick.
• For undirected graphs, track edges by ID to avoid double-using an edge.
• For directed graphs, simply advance the adjacency pointer — each edge is consumed once.
• Real-world applications include DNA sequencing (de Bruijn graphs), circuit testing, and the Chinese Postman Problem.

Quick Reference