Eulerian Path and Circuit

An Eulerian circuit uses every edge exactly once and returns to the start. An Eulerian path uses every edge exactly once without returning. (Contrast with Hamiltonian, which visits every vertex once — and is NP-complete.)

Existence conditions

Undirected (ignoring isolated vertices, and requiring all edges in one component):

	Condition
Eulerian circuit	connected and every vertex has even degree
Eulerian path	connected and exactly two vertices have odd degree (start and end there)

Directed (requiring the graph to be connected when directions are ignored, restricted to vertices with edges):

	Condition
Eulerian circuit	${\mathrm{deg}}^{+}(v)={\mathrm{deg}}^{-}(v)$ for all $v$, and all edges in one strongly connected component
Eulerian path	at most one vertex with ${\mathrm{deg}}^{+}-{\mathrm{deg}}^{-}=1$ (start), at most one with ${\mathrm{deg}}^{-}-{\mathrm{deg}}^{+}=1$ (end), all others balanced

The odd-degree count is always even by the handshake lemma, which is why “exactly two” is the only path case.

Hierholzer’s algorithm — $O(E)$

Walk arbitrarily until stuck, then splice in detours from vertices that still have unused edges. Iteratively:

vector<int> hierholzer(int start, int n, vector<vector<pair<int,int>>>& adj, int m) {
    vector<bool> usedEdge(m, false);
    vector<int> it(n, 0), st = {start}, circuit;
    while (!st.empty()) {
        int u = st.back();
        while (it[u] < (int)adj[u].size() && usedEdge[adj[u][it[u]].second]) it[u]++;
        if (it[u] == (int)adj[u].size()) { circuit.push_back(u); st.pop_back(); }
        else {
            auto [v, id] = adj[u][it[u]++];
            usedEdge[id] = true;
            st.push_back(v);
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;                  // has m+1 vertices if an Eulerian trail exists
}

The it[] pointer is essential: without it, repeatedly scanning for an unused edge makes the algorithm $O(VE)$. See Hierholzer’s Algorithm.

Undirected edge marking

Mark the edge id, not the vertex pair — otherwise parallel edges break. In an undirected graph, both directions of an edge share one id.

Applications

De Bruijn sequences

A cyclic string of length ${\sigma }^n$ over an alphabet of size $\sigma$ containing every length-$n$ string exactly once as a substring. Build a graph whose vertices are $(n-1)$-length strings and whose edges are $n$-length strings; every vertex is balanced, so an Eulerian circuit exists, and reading it off gives the sequence.

Genome assembly

The de Bruijn graph approach to sequence assembly is exactly this — reads become edges, and an Eulerian path reconstructs the sequence. (Contrast the overlap-layout-consensus approach, which is Hamiltonian and therefore intractable.)

Chinese Postman Problem

Traverse every edge at least once, minimising total distance. If the graph is Eulerian, the answer is the total edge weight. Otherwise, find the odd-degree vertices (there are an even number, say $2k$), compute all-pairs shortest paths among them, find a minimum-weight perfect matching on those $2k$ vertices, and duplicate the matched paths. Then the graph is Eulerian.

$\text{answer}={\sum }_e{w}_e+\text{minimum perfect matching among odd-degree vertices}.$

With $2k\le 16$ or so, a bitmask DP over the odd vertices does the matching; otherwise use Blossom.

Other

• Domino / word chains — “arrange these dominoes end to end” is an Eulerian path on a graph whose vertices are the numbers.
• Drawing a figure without lifting the pen — the original Königsberg question.
• Reconstructing a route from turn counts.

Counting Eulerian circuits

The BEST theorem gives the number of Eulerian circuits in a connected directed graph:

$ec(G)=t_w(G)\cdot {\prod }_v({\mathrm{deg}}^{+}(v)-1)!$

where $t_w(G)$ is the number of arborescences rooted at any fixed vertex — computable by the Matrix-Tree theorem. The undirected counting problem is p-complete.

See also: Hierholzer · Hamiltonian Path · Graph Fundamentals