Eulerian Trails & Circuits: Degree Conditions & Hierholzer's O(E) Algorithm

Necessary & Sufficient Degree Conditions

Assume all vertices with non-zero degree belong to a single connected component (or in the directed case, a single weakly connected component whose underlying active vertices satisfy the degree conditions below).

How Hierholzer's Algorithm Splices Sub-Cycles in $O(E)$

Suppose we start at $s$ and greedily follow unused outgoing edges, deleting each edge as we traverse it. By the degree invariant, whenever we enter any vertex $v \neq t$, there is at least one unused outgoing edge leaving $v$. Thus the greedy walk can only get stuck at the destination vertex $t$ (or $s$ for a circuit)!

However, this initial walk $W$ might bypass some edges if the graph contains side-cycles. Instead of splicing linked lists mid-walk, Hierholzer's post-order formulation maintains a per-vertex edge cursor head[u] (just like Dinic's current-arc pointer):

1. While vertex $u$ still has unused outgoing edges, grab the next edge $e = (u, v)$, advance head[u]++, and recurse (or push to an explicit stack) on $v$.
2. Only when $u$ has zero remaining outgoing edges do we append $u$ to the output vector trail.
3. Finally, reverse trail. If trail.size() == E + 1, the graph is connected on its edge set and trail is the exact Eulerian path; otherwise the edges belong to disconnected components!

Complexity Matrix

Production Implementation: Iterative Hierholzer's Algorithm (Directed & Undirected)

#include <vector>
#include <algorithm>

// Finds a Directed Eulerian Trail/Circuit in O(V + E). Returns empty vector if none exists.
std::vector<int> findDirectedEulerianTrail(int n, int m, const std::vector<std::vector<int>>& adj) {
    std::vector<int> in(n, 0), out(n, 0);
    for (int u = 0; u < n; ++u) {
        out[u] = static_cast<int>(adj[u].size());
        for (int v : adj[u]) ++in[v];
    }

    int start = -1, plusOne = 0, minusOne = 0;
    for (int u = 0; u < n; ++u) {
        int diff = out[u] - in[u];
        if (diff == 1) { ++plusOne; start = u; }
        else if (diff == -1) { ++minusOne; }
        else if (diff != 0) return {};
    }
    if (!((plusOne == 0 && minusOne == 0) || (plusOne == 1 && minusOne == 1))) return {};

    if (start == -1) {
        start = 0;
        for (int u = 0; u < n; ++u) {
            if (out[u] > 0) { start = u; break; }
        }
    }

    std::vector<size_t> cursor(n, 0);
    std::vector<int> st = {start}, trail;
    trail.reserve(m + 1);

    while (!st.empty()) {
        int u = st.back();
        if (cursor[u] < adj[u].size()) {
            int v = adj[u][cursor[u]++];
            st.push_back(v);
        } else {
            trail.push_back(u);
            st.pop_back();
        }
    }

    if (static_cast<int>(trail.size()) != m + 1) return {}; // Disconnected edge components
    std::reverse(trail.begin(), trail.end());
    return trail;
}