Eulerian Graph

This page briefly introduces Eulerian graphs, their implementation, and their applications.

Definition

Only finite graphs are considered in this article.

In graph theory, an Eulerian path is a path that traverses every edge of a graph exactly once, while an Eulerian circuit is a circuit that traverses every edge exactly once. A graph containing an Eulerian circuit is called an Eulerian graph; a graph without an Eulerian circuit but with an Eulerian path is called a semi-Eulerian graph.

Properties

Assume below that the graph $G$ has no isolated vertices. This is without loss of generality, because the properties below remain true for the graph $G$ obtained by deleting the isolated vertices of $G$, so the graph $G'$ occurs explicitly twice.

For a connected graph $G$, the following three properties are equivalent:

1. $G$ is Eulerian;
2. every vertex of $G$ has even degree (for a directed graph, every vertex has equal indegree and outdegree);
3. $G$ is the edge-disjoint union of several cycles.

We prove the equivalence below.

If a graph $G$ is Eulerian, every vertex of $G$ has even degree. Start at any vertex and traverse one Eulerian circuit. The degree of a vertex $v$ is the number of departures from $v$ plus the number of arrivals at $v$. Since the walk is a circuit, these two counts are equal for every vertex $v$, so every degree has the form $2k$ and is even. For a directed graph, the same argument shows that every vertex has equal indegree and outdegree.

Conversely, if every vertex of $G$ has even degree (or equal indegree and outdegree), then $u$ is the edge-disjoint union of cycles. Start at any vertex $(u, v)$, choose an incident edge $v$, move to $(u, v)$, and delete $u$. Continue until returning to $u$. The walk must return to $v \neq u$: whenever it reaches a new vertex $v$, the preceding property leaves an odd number of unused incident edges, so the walk cannot stop at $u$. Since $G$ has finitely many edges, the walk stops after finitely many steps and returns to $u$, producing a cycle at $G$. Deleting that cycle leaves a graph with the same property, so repeating the process decomposes the graph into edge-disjoint cycles. Moreover, each cycle can be split at repeatedly visited vertices into an edge-disjoint union of simple cycles, so “simple cycle” may be used in the statement above.

If a connected graph $G$ is the edge-disjoint union of cycles, then $G$ is Eulerian: repeatedly choose two cycles sharing a vertex and merge them into one cycle until no two cycles share a vertex. The final cycle is unique. For any two edge-disjoint cycles $P_1, P_2$, if $P_1$ and $P_2$ share a vertex in $P_1$ they can be merged there. Otherwise choose $v_1$ on $P_2$ and $v_2$ on $G$. Since $v_1$ is connected, there is a path $v_2$ joining $e_1, e_2, \ldots, e_k$ and $e_i$. Each $C_i$ lies on a cycle $P_1$; $C_1$ meets $C_i$, $C_{i+1}$ meets $C_k$, and $P_2$ meets $C_i = C_{i+1}$ (possibly $P_1$). Thus $P_2$ and $C_1, \ldots, C_k$ can be merged through $E(G)$. The unique final cycle has edge set $G$, so it is an Eulerian circuit of $G$.

These properties also give a criterion for Eulerian graphs: a graph is Eulerian if and only if its nonzero-degree vertices are mutually (strongly) connected and all vertices have even degree (or equal indegree and outdegree).

A semi-Eulerian graph has exactly two odd-degree vertices, and these are the endpoints of an Eulerian path. Connecting those two vertices turns it into an Eulerian graph; deleting any edge from an Eulerian graph produces a semi-Eulerian graph. Thus, a graph is semi-Eulerian if and only if its nonzero-degree vertices are mutually (strongly) connected and exactly two vertices have odd degree. For a directed graph, the second condition is that there are exactly two vertices $u, v$ with $\deg^+(u) - \deg^-(u) = 1, \deg^+(v) - \deg^-(v) = -1$, while all other vertices have equal indegree and outdegree.

Constructing Eulerian Circuits and Paths

We introduce the commonly used Hierholzer algorithm. Its central idea is the third Eulerian property above: an Eulerian graph is the edge-disjoint union of cycles. The proof already describes a complete procedure for merging edge-disjoint cycles into an Eulerian circuit. With a suitable data structure, such as a linked-list representation of cycles, the implementation is straightforward.

The algorithm first finds a cycle in the graph as the current cycle. Each time it chooses a vertex on the current cycle with unused incident edges, finds a new simple cycle starting there, and merges it into the current cycle. Once every vertex on the current cycle has no remaining incident edge, the current cycle is an Eulerian circuit.

The algorithm also applies to directed graphs. For a semi-Eulerian graph, start with a path joining the two odd-degree vertices, then repeatedly find a simple cycle at a vertex with unused edges and merge it into the current path; the result is an Eulerian path.

Implementation

The pseudocode for Hierholzer's algorithm is as follows:

Eulerian graph

The time complexity of Hierholzer's algorithm is $O(|E| + |V|)$.

The correctness proof above shows that finding a simple cycle (or the initial path of a semi-Eulerian graph) requires no backtracking: following unused edges always finds the desired cycle or path, and each edge is visited only once. To exploit this property, store edges in a linked-list-like structure, such as an adjacency list or forward-star representation, so that an edge is deleted immediately after it is visited. With a naive adjacency matrix, finding an edge costs $O(|V|)$ each time, giving total complexity $O(|V||E|)$.

To output the lexicographically smallest Eulerian path or circuit, sort the edges. The time complexity is $\Theta(|E|\log |E|)$, or $\Theta(|E|)$ with counting sort or radix sort.

Applications

Directed Eulerian graphs can be used for computer encoding.

Suppose there are $m$ letters. We want a circular disk with $m^n$ sectors, one letter per sector, such that every consecutive $n$ sectors spell a distinct string of length $n$. After one complete rotation ($m^n$ steps), we obtain the strings produced by the $m$ letters, $n$ letters long, all $m^n$ of them distinct.

Construct the following directed Eulerian graph:

Let $S = \{a_1, a_2, \cdots, a_m\}$ and construct $D=\langle V, E\rangle$ as follows:

$V = \{a_{i_1}a_{i_2}\cdots a_{i_{n-1}} |a_i \in S, 1 \leq i \leq n - 1 \}$

$E = \{a_{j_1}a_{j_2}\cdots a_{j_{n-1}}|a_j \in S, 1 \leq j \leq n\}$

Define the incidence of vertices and edges in $D$ as follows:

The vertex $a_{i_1}a_{i_2}\cdots a_{i_{n-1}}$ has $m$ outgoing edges: $a_{i_1}a_{i_2}\cdots a_{i_{n-1}}a_r, r=1, 2, \cdots, m$.

The edge $a_{j_1}a_{j_2}\cdots a_{j_{n-1}}$ enters the vertex $a_{j_2}a_{j_3}\cdots a_{j_{n}}$.

This $D$ is connected, and every vertex has indegree equal to outdegree (both equal to $m$), so $D$ is a directed Eulerian graph.

In $D$, find an Eulerian circuit $C$. Take the last letter of each edge of $C$ and place the letters around the disk in the order in which the edges occur in $C$.

Example

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct edge {
  int to;
  bool exists;
  int revref;

  bool operator<(const edge& b) const { return to < b.to; }
};

vector<edge> beg[505];
int cnt[505];

constexpr int dn = 500;
stack<int> ans;

void Hierholzer(int x) {  // core routine
  for (int& i = cnt[x]; i < (int)beg[x].size();) {
    if (beg[x][i].exists) {
      edge e = beg[x][i];
      beg[x][i].exists = beg[e.to][e.revref].exists = false;
      ++i;
      Hierholzer(e.to);
    } else {
      ++i;
    }
  }
  ans.push(x);
}

int deg[505];
int reftop[505];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  for (int i = 1; i <= dn; ++i) {
    beg[i].reserve(1050);  // reserve avoids dynamic allocation and improves speed
  }

  int m;
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    beg[a].push_back(edge{b, true, 0});
    beg[b].push_back(edge{a, true, 0});
    ++deg[a];
    ++deg[b];
  }

  for (int i = 1; i <= dn; ++i) {
    if (!beg[i].empty()) {
      sort(beg[i].begin(), beg[i].end());  // sort for lexicographic greedy selection
    }
  }

  for (int i = 1; i <= dn; ++i) {
    for (int j = 0; j < (int)beg[i].size(); ++j) {
      beg[i][j].revref = reftop[beg[i][j].to]++;
    }
  }

  int bv = 0;
  for (int i = 1; i <= dn; ++i) {
    if (!deg[bv] && deg[i]) {
      bv = i;
    } else if (!(deg[bv] & 1) && (deg[i] & 1)) {
      bv = i;
    }
  }

  Hierholzer(bv);

  while (!ans.empty()) {
    cout << ans.top() << '\n';
    ans.pop();
  }
}

Exercises

• SGU 101 Domino

• POJ 1780 Code

• Luogu P1127 Word Chain

• Luogu P1333 Ruirui's Sticks

• Luogu P1341 Unordered Letter Pairs

• Luogu P6066 [USACO05JAN] Watchcow S

• Luogu P6628 [National Selection 2020 B] Lilac Road

• Luogu P3520 [POI 2011] SMI-Garbage