xvi. Euler Tours

An Eulerian circuit uses every edge exactly once and returns; an Eulerian path does not need to return. Unlike the Hamiltonian (vertex) version, existence is a local degree condition and Hierholzer finds one in $O(n+m)$. Applications: de Bruijn sequences, route inspection (Chinese postman), balanced orientations, splitting bipartite graphs into matchings, and many constructive problems where “each item is used once” becomes “each edge is traversed once”.

	Undirected	Directed
circuit	all degrees even, edges in one component	${\mathrm{deg}}^{+}={\mathrm{deg}}^{-}$ everywhere, edges in one weak component
path	exactly 0 or 2 odd vertices (start at an odd one)	one vertex $+1$ (start), one $-1$ (end), others balanced, one weak component

Proof: the degree conditions

Necessity: every pass through a vertex uses one edge in and one out, so internal visits use edges in pairs; only the endpoints of an open trail have odd degree (or unbalanced in/out). Sufficiency (circuit): start anywhere and walk along unused edges; when the walk enters $v\ne$ start, $v$ has an unused edge left (it has used an odd number of its edges at that moment, and its degree is even), so the walk can only get stuck at the start: it is a closed trail $C$. If edges remain, connectivity gives a vertex of $C$ with an unused edge; the unused edges still satisfy the degree condition, so a closed trail starts and ends there and can be spliced into $C$. Repeat. Path: add an edge between the two odd vertices (or from the $-1$ to the $+1$ vertex), take a circuit, remove the edge. In the directed case “weakly connected + balanced” implies strongly connected on the edges, since a balanced digraph is a union of directed cycles.

Hierholzer

vector<int> eulerWalk(int n, const vector<pair<int, int>>& E, bool directed, int start) {   // vertex sequence, empty if none
    vector<vector<pair<int, int>>> g(n); vector<int> deg(n);
    for (int i = 0; i < sz(E); i++) {
        auto [u, v] = E[i]; g[u].push_back({v, i}); deg[u]++;
        if (directed) deg[v]--; else g[v].push_back({u, i}), deg[v]++;
    }
    int bad = 0;                                            // degree conditions for a trail starting at `start`
    for (int v = 0; v < n; v++) {
        if (directed) { if (deg[v] != 0 && !(v == start && deg[v] == 1) && deg[v] != -1) return {}; bad += deg[v] == -1; }
        else if (deg[v] % 2) { bad++; }
    }
    if (directed ? bad > 1 || (bad == 1) != (deg[start] == 1) : bad > 2 || (bad == 2 && deg[start] % 2 == 0)) return {};
    vector<char> used(sz(E)); vector<int> it(n), st{start}, res;
    while (sz(st)) {
        int u = st.back();
        while (it[u] < sz(g[u]) && used[g[u][it[u]].second]) it[u]++;
        if (it[u] == sz(g[u])) { res.push_back(u); st.pop_back(); }
        else { auto [v, id] = g[u][it[u]++]; used[id] = 1; st.push_back(v); }
    }
    reverse(all(res));
    if (sz(res) != sz(E) + 1) return {};                    // not all edges reached: disconnected
    return res;   // pick start = an odd vertex (undirected) or the vertex with out - in = +1 (directed) when one exists
}

Store edge ids to handle parallel edges and to output edges instead of vertices; the it[] pointer makes it linear. To output the sequence of edges, push the id together with the vertex.

Mark the edge id, not the vertex pair

With parallel edges, used[v] or used[{u,v}] is wrong — two distinct parallel edges between the same pair would be conflated. Always mark used[edge_id]; in an undirected graph both directions of an edge share one id, so marking it from either side is correct.

Chinese postman (route inspection)

Shortest closed walk using every edge at least once. Undirected: total weight + minimum-weight perfect matching of the odd-degree vertices under shortest-path distances (duplicate the matched paths, then everything is even). With $k\le 20$ odd vertices a bitmask DP that always matches the lowest unmatched vertex; otherwise weighted general matching (Weighted Matching). Directed: min-cost flow from vertices with excess in-degree to vertices with excess out-degree. Mixed graphs (some directed, some undirected edges): NP-hard.

ll chinesePostman(int n, const vector<array<ll, 3>>& E) {    // {u, v, w}; -1 if the edges are disconnected
    const ll INF = LLONG_MAX / 4; vector<vector<ll>> d(n, vector<ll>(n, INF)); vector<int> deg(n), p(n); iota(all(p), 0);
    auto f = [&](int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; };
    ll total = 0; for (int i = 0; i < n; i++) d[i][i] = 0;
    for (auto [u, v, w] : E) d[u][v] = min(d[u][v], w), d[v][u] = min(d[v][u], w), deg[u]++, deg[v]++, total += w, p[f(u)] = f(v);
    for (auto [u, v, w] : E) if (f(u) != f(E[0][0])) return -1;
    for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    vector<int> odd; for (int v = 0; v < n; v++) if (deg[v] % 2) odd.push_back(v);
    int k = sz(odd); vector<ll> dp(1 << k, INF); dp[0] = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        if (dp[mask] >= INF) continue;
        int i = 0; while (i < k && (mask >> i & 1)) i++;
        if (i == k) continue;
        for (int j = i + 1; j < k; j++) if (!(mask >> j & 1)) dp[mask | 1 << i | 1 << j] = min(dp[mask | 1 << i | 1 << j], dp[mask] + d[odd[i]][odd[j]]);
    }
    return total + dp[(1 << k) - 1];
}

Proof: the matching formula

A closed walk covering every edge traverses each edge $e$ some $c_e\ge 1$ times; the multigraph with $c_e$ copies is Eulerian, so the extra copies ($c_e-1$) form a set $X$ of edges in which exactly the odd-degree vertices of $G$ have odd degree. Such an $X$ decomposes into paths pairing up the odd vertices plus cycles; dropping cycles (nonnegative weight) and replacing each path by a shortest path doesn’t increase the cost. So the minimum extra cost is the minimum-weight perfect matching of the odd vertices under shortest-path distance, and conversely any such matching gives a valid Eulerian multigraph.

De Bruijn sequences

A cyclic sequence over $k$ symbols containing every length-$n$ word exactly once has length $k^n$; it is an Eulerian circuit in the graph whose vertices are the $k^{n-1}$ words of length $n-1$ and whose edges are the length-$n$ words (every vertex has in- and out-degree $k$). The lexicographically smallest one is the concatenation, in lexicographic order, of all Lyndon words whose length divides $n$ (FKM algorithm):

vector<int> deBruijn(int k, int n) {                       // cyclic, length k^n, symbols 0..k-1
    vector<int> res, w{-1};
    while (sz(w)) {                                         // w runs over Lyndon words of length <= n in order
        w.back()++; int m = sz(w);
        if (n % m == 0) res.insert(res.end(), all(w));
        while (sz(w) < n) w.push_back(w[sz(w) - m]);
        while (sz(w) && w.back() == k - 1) w.pop_back();
    }
    return res;
}

As a linear string, append the first $n-1$ symbols again: length $k^n+n-1$, optimal. For variants (forbidden words, fixed start) run Hierholzer on the de Bruijn graph instead. Genome assembly from short reads is exactly this: reads (or their overlaps) are the graph’s edges, and assembling the genome is an Eulerian path — the de Bruijn-graph approach, as opposed to the Hamiltonian overlap-layout-consensus approach, which is why de Bruijn assemblers scale and Hamiltonian ones don’t.

Counting Eulerian circuits: BEST theorem

For a connected balanced digraph, $\text{ec}(G)=t_w(G){\prod }_v({\mathrm{deg}}^{+}(v)-1)!$, where $t_w$ is the number of arborescences oriented into any fixed vertex $w$ (directed matrix-tree theorem, Matrix-Tree); circuits are counted up to rotation (fix the first edge out of $w$). Counting Eulerian circuits in undirected graphs is p-complete.

Proof sketch: BEST

Fix a starting edge out of $w$. For an Eulerian circuit, record for every vertex $v\ne w$ the last edge by which the circuit leaves $v$; these edges form an arborescence into $w$ (following last exits from any vertex never cycles, since after the last exit from $v$ the circuit never returns to $v$, and it must end at $w$). Conversely, given an arborescence into $w$ and, for every vertex, an ordering of its other out-edges (with $w$‘s first edge fixed), the circuit that at each visit to $v$ takes the next out-edge in that order, using the arborescence edge last, is a valid Eulerian circuit. This is a bijection, giving $t_w\cdot {\prod }_v({\mathrm{deg}}^{+}(v)-1)!$.

Euler tours as a construction tool

• Balanced orientation: orient the edges of an undirected graph so that $|{\mathrm{deg}}^{+}-{\mathrm{deg}}^{-}|\le 1$ everywhere: join all odd vertices to a dummy vertex, take Euler circuits of each component, orient along them, drop the dummy edges.
• Splitting into two halves: an Eulerian circuit of a graph with all even degrees, with edges alternately coloured, gives each vertex exactly half of its edges in each colour (for even-length circuits); this splits a $2k$-regular bipartite graph into two $k$-regular ones, the basis of fast bipartite edge colouring (Colouring).
• Minimum number of trails covering all edges of a connected graph: $\max (1,\#\text{odd}/2)$.
• Grid / matrix construction problems (“each row and column balanced”, “arrange dominoes in a chain”, “sequence where each pair appears once”, “reconstruct an itinerary/route from a set of tickets or turn counts”): build the bipartite or line graph, check degrees, run Hierholzer.

Proof: balanced orientation

After adding a dummy vertex adjacent to every odd vertex, all degrees are even (the dummy has even degree because the number of odd vertices is even), so each component has an Eulerian circuit. Orienting along it gives every vertex in-degree = out-degree in the augmented graph; removing the dummy edges changes each original vertex’s in/out difference by at most one (each odd vertex lost exactly one dummy edge), so $|{\mathrm{deg}}^{+}-{\mathrm{deg}}^{-}|\le 1$.

Related

• The Königsberg bridges problem is the historical origin of this whole topic — see Seven Bridges of Königsberg for Euler’s original argument and the modern (post-1944, Kaliningrad) bridge count.
• The degree-condition proof above is the archetype of an invariant/parity impossibility proof: find a quantity every move preserves, show the goal is incompatible with it. The same move proves the 15-puzzle unsolvable for odd permutations, the mutilated chessboard untileable, and the closed knight’s tour impossible on odd boards.