Eulerian Circuit

Topic type: Algorithm Paradigm (Graph) LeetCode problems: ~15–25

See graph-theory.md for graph fundamentals (degree, connectivity, adjacency list, directed vs. undirected). See depth-first-search.md for DFS mechanics used as the backbone of Hierholzer's algorithm.

---

Core Concepts

Eulerian path — a walk through a graph that visits every edge exactly once. The walk need not return to its starting vertex.

Eulerian circuit (Eulerian tour) — an Eulerian path that starts and ends at the same vertex. Also called an Eulerian cycle.

Semi-Eulerian graph — a graph that contains an Eulerian path but not an Eulerian circuit; has exactly two vertices of odd degree (undirected) or exactly one source vertex and one sink vertex (directed).

Degree condition (undirected) — an Eulerian circuit exists if and only if the graph is connected (ignoring isolated vertices) and every vertex has even degree. An Eulerian path exists when exactly 0 or 2 vertices have odd degree; the path starts and ends at the odd-degree vertices.

Degree condition (directed) — an Eulerian circuit exists if and only if the graph is strongly connected (on vertices with non-zero degree) and every vertex has in-degree = out-degree. An Eulerian path exists when exactly one vertex has out-degree − in-degree = 1 (start) and exactly one has in-degree − out-degree = 1 (end), all others balanced.

Hierholzer's algorithm — the standard O(V + E) algorithm for constructing an Eulerian circuit or path. Builds the tour via DFS with a post-order push: a vertex is appended to the result only after all its outgoing edges have been exhausted.

Fleury's algorithm — an older O(E²) algorithm that builds the circuit by greedily choosing non-bridge edges. Correct but too slow for competitive use; never chosen in practice over Hierholzer's.

Chinese Postman Problem — find the minimum-weight closed walk that traverses every edge at least once. On undirected graphs: find minimum-weight perfect matching on odd-degree vertices and duplicate the matched edges. On directed graphs with unbalanced vertices: find a min-cost flow to balance degrees, then find an Eulerian circuit.

BEST theorem — counts the number of distinct Eulerian circuits in a directed graph. Result = (number of arborescences rooted at any vertex) × ∏ᵥ (out-degree(v) − 1)!. Used for counting problems (e.g., LeetCode 753 Cracking the Safe).

Edge used / edge index tracking — because Hierholzer's must not reuse edges, directed graphs track which outgoing edges have been consumed (an index per vertex advancing through the adjacency list). Undirected graphs mark each edge used in both directions.

---

Types / Variants

---

Key Algorithms

Hierholzer's Algorithm

Constructs an Eulerian circuit (or path) in O(V + E) time, O(V + E) space. The key insight: begin a DFS from the start vertex, always taking an available edge; when stuck (no more edges from current vertex), push the current vertex onto the result stack. The result, reversed, is the Eulerian circuit. This works because any vertex you get stuck at must be the start (for circuits) or the designated end (for paths) — all other vertices have even degree so they always allow an exit whenever they are entered.

For directed graphs, track a pointer ptr[v] into the adjacency list of v so each call to the next edge is O(1) amortised:

ptr = {v: 0 for v in graph}
def dfs(v):
    while ptr[v] < len(graph[v]):
        u = graph[v][ptr[v]]; ptr[v] += 1; dfs(u)
    result.append(v)

Reverse result at the end. For an Eulerian path (not circuit), start DFS from the vertex with out − in = 1; if all balanced, start from any vertex with edges.

For undirected graphs, represent each edge as an index and mark edges used to avoid traversing both directions:

used = set()   # edge indices
for i, (u, w) in enumerate(adj[v]):
    if i not in used: used.add(i); dfs(w)

Existence Check Before Running Hierholzer's

Always verify existence conditions before attempting to construct the path; construction on a graph without an Eulerian circuit will silently produce a partial result.

For directed graphs:

for v in graph:
    if in_deg[v] != out_deg[v]: return []   # no circuit

For undirected, count vertices with odd degree; return early if the count is not 0 (circuit) or 2 (path).

Fleury's Algorithm

Constructs the Eulerian circuit by walking edges one at a time, always preferring non-bridge edges. O(E²) due to repeated bridge-detection (Tarjan's) at each step. Use only to understand the correctness argument; always prefer Hierholzer's in practice.

Chinese Postman on Undirected Graphs

1. Find all vertices with odd degree — there are always an even number of them.
2. Compute shortest paths between every pair of odd-degree vertices (Dijkstra or Floyd-Warshall).
3. Find a minimum-weight perfect matching on the odd-degree vertices (blossom algorithm or DP on bitmask for small sets).
4. Add the shortest-path edges for each matched pair (duplicating them in the graph).
5. Find an Eulerian circuit on the augmented graph.

Time: O(V³) for shortest paths + O(2^k · k²) for bitmask DP matching where k = number of odd-degree vertices.

Chinese Postman on Directed Graphs

Model degree imbalances as a supply/demand problem: each vertex with out − in > 0 is a source; in − out > 0 is a sink. Use min-cost max-flow to route supply to demand via shortest paths. Once all degrees are balanced, run Hierholzer's. O(V·E·log V) with SPFA-based min-cost flow.

---

Advanced Techniques

Edge-Index Pointer (Hierholzer's on Dense Adjacency Lists)

Sorting the adjacency list lexicographically once before running Hierholzer's guarantees the lexicographically smallest Eulerian path (required by LeetCode 332). Without sorting, any valid Eulerian path is produced. The pointer ptr[v] advancing through a sorted list costs O(E) total, not O(E) per vertex. Use this over repeated edge removal (which would cost O(E²)) whenever the adjacency list is long.

When to prefer it over naive edge popping: always for directed graphs; for undirected graphs where lexicographic order is required, sorting edges per vertex before the DFS.

De Bruijn Sequence via Eulerian Circuit

A De Bruijn sequence of order n over an alphabet of size k is a cyclic sequence in which every possible string of length n appears as a substring exactly once. Model: vertices = (n−1)-grams, edges = n-grams. An Eulerian circuit on this graph produces the De Bruijn sequence. This directly underlies LeetCode 753 (Cracking the Safe): treat the dial as a De Bruijn sequence problem.

When to use over brute-force DFS: whenever the problem asks for a shortest cyclic sequence containing all strings of a fixed length — the Eulerian circuit on the De Bruijn graph is optimal by construction and runs in O(k^n) vs. exponential brute force.

T-Join / Bitmask DP for Small Chinese Postman

When the number of odd-degree vertices k ≤ 20, use bitmask DP for minimum-weight perfect matching instead of the full blossom algorithm. State: dp[mask] = min cost to perfectly match all vertices in mask. Transition: pick the lowest-set-bit vertex, try all other vertices in mask as its partner.

dp[mask] = min(dist[u][v] + dp[mask ^ (1<<i) ^ (1<<j)]
               for j, v in enumerate(odd) if mask>>j&1 and j != i)

Use this over blossom when k is small (competitive programming constraints typically have k ≤ 12–16). Blossom is needed for k up to O(V).

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Disconnected graph with isolated vertices: the Eulerian circuit condition "all even degrees" is not sufficient alone — the graph must also be connected (ignoring zero-degree vertices). Failing to check connectivity produces a partial circuit covering only one connected component. Fix: verify that all vertices with non-zero degree belong to one connected component (BFS/DFS from any edge-incident vertex).

• Directed graph connectivity check: for directed graphs, checking in-degree = out-degree for all vertices is necessary but not sufficient — the graph must also be weakly connected (treating edges as undirected) for an Eulerian circuit to exist, and there must be a single weakly connected component containing all edges. A common mistake is to skip the connectivity check and get a partial result.

• Starting vertex for directed Eulerian path: always start Hierholzer's from the vertex with out − in = 1 (if it exists). Starting from a balanced vertex when a path (not circuit) is required will produce a tour that misses edges or cannot close. If no such vertex exists, the graph has a circuit and any vertex with edges is a valid start.

• Lexicographic order requirement (LeetCode 332): sorting adjacency lists once before DFS is not enough if using a mutable list with pop() — pop() from the front is O(n). Use pop() from the back (i.e., reverse-sort and pop from the end) to get lexicographic order in O(1) per edge removal. Alternatively, use the ptr[v] pointer on a sorted list.

• Multigraph: tracking edges by (u, v) pair: if there are multiple edges between the same pair of vertices, marking (u, v) as "used" after the first traversal prevents using the second edge. Always track by edge index.

• Undirected graph: marking both directions: each undirected edge appears in both adj[u] and adj[v]. When marking an edge used, mark it in both directions or use a shared edge-index set. Failing to do this causes the same edge to be traversed twice.

• Result must be reversed: Hierholzer's appends in post-order (deepest-first). The final result is in reverse order of the actual path. Always reverse before returning.

• Empty graph / no edges: if the graph has no edges, the only valid Eulerian circuit is the trivial one (staying at the start). Return [start] not []. Many implementations incorrectly return an empty list.

• Graph with one vertex and a self-loop: valid Eulerian circuit of length 1. The degree is 2 (self-loop contributes 2 to degree), so the even-degree condition holds. Hierholzer's handles this correctly only if the self-loop is represented as a proper edge entry.

---

Implementation Notes

• Python's default recursion limit (~1000) will be exceeded on graphs with E > ~500 if Hierholzer's is implemented recursively. Use an iterative stack-based implementation for all non-trivial inputs.
• collections.defaultdict(list) is the natural adjacency list; sorting each list once before the DFS achieves lexicographic output without changing the asymptotic complexity.
• For LeetCode 332 specifically, the iterative Hierholzer's using a stack and result.append + result.reverse() at the end is the standard accepted pattern; recursive implementations hit recursion limits on large test cases.
• Python's heapq (min-heap) can replace a sorted list for the adjacency structure when dynamic insertion is needed, but for static graphs, sort once and use a pointer.
• When computing degree balance for directed graphs, use two dicts (in_deg, out_deg) built during adjacency list construction rather than post-processing, to avoid an extra O(V + E) pass.
• The BEST theorem requires computing the number of arborescences via Kirchhoff's matrix-tree theorem (determinant of a reduced Laplacian). In Python, use numpy.linalg.det or implement Gaussian elimination; be careful about integer overflow for large graphs.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Eulerian Path Construction

• LeetCode 332 — Reconstruct Itinerary (directed Eulerian path; lexicographically smallest; canonical Hierholzer's application)
• LeetCode 2097 — Valid Arrangement of Pairs (directed Eulerian path; identical structure to 332 but without the lexicographic requirement; tests existence check)

De Bruijn / Sequence Coverage

• LeetCode 753 — Cracking the Safe (De Bruijn sequence via Eulerian circuit on k-mer graph; hard)

Route Inspection / Chinese Postman

• Classic competitive programming: "Minimum additional edges to make graph Eulerian" (add edges between odd-degree vertices via minimum matching)
• Variant: "Minimum cost to traverse all edges" (Chinese Postman; add duplicated edges for cheapest route)

Existence and Degree Conditions

• LeetCode 1971 — Find if Path Exists in Graph (connectivity prerequisite, not Eulerian itself, but part of the existence check)
• Any problem asking "can all items be arranged in a single sequence using each exactly once" — map to directed Eulerian path existence

Clarification Questions to Ask

• Are there duplicate edges (multigraph)? This affects how edges are tracked during Hierholzer's.
• Is the graph directed or undirected? The degree conditions differ entirely.
• Is lexicographic ordering of the result required? Changes adjacency list handling.
• Must the path be a circuit (return to start) or can it be an open path?
• Are isolated vertices (degree 0) present? They do not affect Eulerian conditions but may affect connectivity checks.
• Can the graph be disconnected with multiple components? Eulerian circuit requires a single connected component over all edges.
• For Chinese Postman: are edge weights given, or is the graph unweighted?

Common Interview Mistakes

• Running Hierholzer's without checking existence conditions first, then getting confused when the result is shorter than expected.
• Checking only degree conditions and forgetting connectivity — a graph can have all even degrees across two disconnected components and still have no Eulerian circuit.
• For directed graphs, using weak connectivity check (treat as undirected) when strong connectivity is required; or checking strong connectivity when weak is sufficient (for Eulerian path, weak + degree balance is correct).
• Sorting the adjacency list and then using list.pop(0) (O(n) per pop) instead of reversing and using list.pop() (O(1)), causing O(E²) total time.
• Reversing the result after using append in Hierholzer's — forgetting the reverse step produces the path in reverse order.
• Confusing "all vertices have even degree" (circuit) with "exactly 2 vertices have odd degree" (path) and applying the wrong condition.
• In undirected graphs, failing to mark the edge used in both adjacency lists, allowing the same physical edge to be traversed twice.

Typical Follow-Up Escalations

• "Now return the lexicographically smallest path" → sort each adjacency list in ascending order before running Hierholzer's; for directed graphs, reverse-sort and pop from the end.
• "Now find the minimum cost to traverse every edge at least once" → Chinese Postman: find odd-degree vertices, run all-pairs shortest paths, apply bitmask DP matching, sum original edge weights + matching cost.
• "Now count the number of distinct Eulerian circuits" → BEST theorem: compute the number of arborescences via the matrix-tree theorem (Kirchhoff's theorem), multiply by ∏ᵥ (out_deg(v) − 1)!.
• "The graph may be disconnected — handle gracefully" → add connectivity check; if edges span multiple components, return empty/impossible.
• "Now do it on an undirected graph" → change degree condition (even degree for all vertices), change edge tracking to use edge indices shared between both endpoint adjacency entries.