Skip to content

Eulerian Graph

This page briefly introduces the concepts, implementation, and applications of Eulerian graphs.

Definition

This article only discusses finite graphs.

In graph theory, an Eulerian path is a path that traverses each edge of the graph exactly once, and an Eulerian circuit is a circuit that traverses each edge exactly once.
A graph that contains an Eulerian circuit is called an Eulerian graph; a graph that does not contain an Eulerian circuit but contains an Eulerian path is called a semi-Eulerian graph.

Warning

Although the term "path" is used in the definition above, strictly speaking, the concept used here should be "trail". Eulerian paths and circuits must use each edge exactly once, but there is no restriction on the vertices visited.

Properties

In the following, we assume that the graph \(G\) under discussion has no isolated vertices. This assumption does not lose generality, because for a graph \(G\) with isolated vertices, the following properties still hold for the graph \(G'\) obtained by removing the isolated vertices from \(G\).

For a connected graph \(G\), the following three properties are equivalent:

  1. \(G\) is Eulerian;
  2. All vertices in \(G\) have even degree (for directed graphs, the in-degree equals the out-degree for each vertex);
  3. \(G\) can be decomposed into a union of edge-disjoint circuits.

Below we prove the equivalence.

If a graph \(G\) is Eulerian, then all vertices in \(G\) have even degree: Consider starting from any vertex and walking along an Eulerian circuit once. Then the degree of each vertex \(v\) equals the number of times leaving \(v\) plus the number of times arriving at \(v\). Since the walk is a circuit, for each vertex \(v\), the number of times leaving equals the number of times arriving. This means the degree of each vertex is of the form \(2k\), i.e., even.
In particular, for directed graphs, by the same proof, the in-degree equals the out-degree for each vertex.

If all vertices in a graph \(G\) have even degree (or in-degree equals out-degree), then it can be decomposed into a union of edge-disjoint circuits: Start from any vertex \(u\), choose any outgoing edge \((u, v)\), move to the adjacent vertex \(v\) and delete \((u, v)\), until returning to the starting vertex \(u\). It can be proved that this process must eventually return to \(u\): Whenever a new vertex \(v \neq u\) is reached, by the previous property, the remaining degree of this vertex is odd, meaning there must be an outgoing edge, so the process does not terminate at \(v\). (In other words, the process stops if and only when returning to \(u\).) Since the number of edges in \(G\) is finite, the process must stop in finite steps, so it must eventually return to \(u\), yielding a circuit. Note that in the above proof we only used the property that all vertices have even degree, and after finding and deleting a circuit, the remaining graph still satisfies this property. We can repeat this process until the remaining graph is empty, thereby decomposing \(G\) into several edge-disjoint circuits.
Furthermore, each circuit can be decomposed at vertices it passes multiple times into a union of disjoint simple cycles, so the simple circuits in the above property can also be replaced by simple cycles.

If a connected graph \(G\) can be decomposed into a union of edge-disjoint circuits, then \(G\) is Eulerian: For a set of edge-disjoint circuits, repeatedly select two circuits that share a common vertex and merge them into one, until no two circuits share a common vertex.
It can be proved that the remaining circuit at the end is unique. For any two edge-disjoint circuits \(P_1, P_2\), if \(P_1\) and \(P_2\) share a vertex, they can be merged directly at that vertex; otherwise, pick any vertex \(v_1\) on \(P_1\) and \(v_2\) on \(P_2\). By connectivity of \(G\), there exists a path \(e_1, e_2, \ldots, e_k\) connecting \(v_1\) and \(v_2\), where each edge \(e_i\) is contained in some circuit \(C_i\), and \(P_1\) shares a vertex with \(C_1\), \(C_i\) shares a vertex with \(C_{i+1}\), and \(C_k\) shares a vertex with \(P_2\) (or \(C_i = C_{i+1}\), which does not affect the proof). In this case, \(P_1\) and \(P_2\) can be merged via \(C_1, \ldots, C_k\). That is, any two circuits can be merged, so the final remaining circuit must be unique, and the edge set of this circuit is the union of all edge-disjoint circuits, i.e., \(E(G)\). This circuit is an Eulerian circuit on \(G\), so \(G\) is Eulerian.

The above properties also constitute the criteria for determining Eulerian graphs. Specifically, a graph is Eulerian if and only if its non-zero-degree vertices are (strongly) connected, and all vertices have even degree (or in-degree equals out-degree).

For semi-Eulerian graphs, the properties are similar: A semi-Eulerian graph has exactly two vertices of odd degree, and these two vertices are the endpoints of the Eulerian path. By connecting these two vertices, a semi-Eulerian graph can be transformed into an Eulerian graph. By deleting any edge from an Eulerian graph, a semi-Eulerian graph can be obtained.
This leads to the criterion for semi-Eulerian graphs: A graph is semi-Eulerian if and only if its non-zero-degree vertices are (strongly) connected, and there are exactly two vertices of odd degree. For directed graphs, the second condition becomes: There exist exactly two vertices \(u, v\) such that \(\deg^+(u) - \deg^-(u) = 1, \deg^+(v) - \deg^-(v) = -1\), and for all other vertices, in-degree equals out-degree.

Construction of Eulerian Circuits/Paths

Here we introduce the most commonly used Hierholzer's algorithm. The core idea of this algorithm is to use the third property of Eulerian graphs mentioned above, i.e., an Eulerian graph can be decomposed into a union of edge-disjoint circuits.
Note that the proof above already describes a complete feasible operation for merging edge-disjoint circuits into an Eulerian circuit, and implementation is not difficult with appropriate data structures (e.g., using a linked-list-like structure to store cycles).

The specific procedure of the algorithm is: First find a circuit in the graph as the current circuit. Then repeatedly pick a vertex from the current circuit that still has remaining degree, find a new simple circuit starting from that vertex, and merge it with the current circuit. Repeat until all vertices in the current circuit have zero remaining degree. The resulting current circuit is an Eulerian circuit.

This algorithm also works for directed graphs. For semi-Eulerian graphs, start by finding a path connecting the two odd-degree vertices as the current path. Then repeatedly pick a vertex with non-zero degree, find a simple circuit, and merge it with the current path, finally obtaining an Eulerian path.

Implementation

The pseudocode for Hierholzer's algorithm is as follows:

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v) \\ 2 & \textbf{Output. } \text{The vertex of the Euler Road of the input graph}.\\ 3 & \textbf{Method. } \\ 4 & \textbf{Function } \text{Hierholzer } (v) \\ 5 & \qquad circle \gets \text{Find a Circle in } e \text{ Begin with } v \\ 6 & \qquad \textbf{if } circle=\varnothing \\ 7 & \qquad\qquad \textbf{return } v \\ 8 & \qquad e \gets e-circle \\ 9 & \qquad \textbf{for} \text{ each } v \in circle \\ 10& \qquad\qquad v \gets \text{Hierholzer}(v) \\ 11& \qquad \textbf{return } circle \\ 12& \textbf{Endfunction}\\ 13& \textbf{return } \text{Hierholzer}(\text{any vertex}) \end{array} \]

Time Complexity Analysis

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

Note that in the correctness analysis above, the process of finding a simple circuit (or the initial path for a semi-Eulerian graph) on an Eulerian or semi-Eulerian graph is backtracking-free: as long as we keep walking along the remaining edges, we are guaranteed to find the desired circuit or path, and each edge is visited exactly once.
To utilize this property, the implementation should store edges in a linked-list-like manner, such as adjacency lists or forward stars, so that each edge is deleted immediately after being visited. If a naive adjacency matrix is used, each edge search takes \(O(|V|)\), leading to a total complexity of \(O(|V||E|)\).

Note

In fact, the precise complexity of this algorithm should be \(O(|E|)\) rather than \(O(|V| + |E|)\), because the implementation can rely on edges rather than vertices by maintaining a global linked list of remaining edges to find the next circuit.

If the lexicographically smallest Eulerian path or circuit needs to be output, the edges must be sorted, resulting in a time complexity of \(\Theta(|E|\log |E|)\) or \(\Theta(|E|)\) (using counting sort or radix sort).

Applications

Directed Eulerian graphs can be used in computer decoding.

Suppose there are \(m\) letters, and we want to construct a disk with \(m^n\) sectors, each sector containing one letter, such that every consecutive \(n\) positions on the disk correspond to a string of length \(n\). After one full rotation (\(m^n\) steps), we obtain \(m^n\) distinct strings of length \(n\) generated from the \(m\) letters.

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 relation in \(D\) as:

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\).

Edge \(a_{j_1}a_{j_2}\cdots a_{j_{n-1}}\) enters vertex \(a_{j_2}a_{j_3}\cdots a_{j_{n}}\).

Such \(D\) is connected, and each vertex has in-degree equal to out-degree (both equal to \(m\)), so \(D\) is a directed Eulerian graph.

Find any Eulerian circuit \(C\) in \(D\), take the last letter of each edge in \(C\), and arrange them in the order of edges in \(C\) on the disk.

Example Problems

Luogu P2731 Riding the Fences

Given an undirected graph with 500 vertices, find an Eulerian path or circuit of this graph. If there are multiple solutions, output the smallest one.

In this problem, the Eulerian path or circuit does not need to visit all vertices.

The number of edges m satisfies \(1\leq m \leq 1024\).

Solution Idea

This problem is a direct application of Hierholzer's algorithm.

The answer can be stored using std::stack<int>, because if the found path is not a circuit, that part must be placed at the end.

Note: Do not use an adjacency matrix to store the graph, otherwise the time complexity degrades to \(\Theta(nm)\). Since edges need to be sorted, it is recommended to use forward stars or std::vector. The sample code uses std::vector.

Sample Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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) {  // Key function
  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);  // Use reserve for vector to avoid dynamic allocation and speed up
  }

  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());  // Must sort for lexicographically greedy traversal
    }
  }

  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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用