A circuit $C$ in a graph $G$ is called an Eulerian circuit if $C$ contains every edge of $G$ (remember that a circuit is a closed trail, i.e., a walk in which no edge is traversed more than once and that begins and ends at the same vertex).

• Every edge of $G$ appears only once in the circuit.
• Only graphs with one component can contain such a circuit.

A connected graph $G$ that contains an Eulerian circuit $C$ is called an Eulerian Graph.

An Eulerian trail is an open trail $T$ that contains all the edges of $G$ (but doesn’t end in the same start vertex).

Königsberg Bridge Problem

The city of Königsberg, located in Prussia, was separated by a river into four land areas. To travel between these areas, seven bridges were built. Some citizens wondered whether it was possible to go for a walk in Königsberg and pass over each bridge exactly once.

In graph theory terms, the problem can be stated as follows:

Does the multigraph $M$ of order $n=4$ and size $m=7$ contain an Eulerian circuit or an Eulerian trail?

Suppose that such a journey is possible. Then it must begin at some land area and end at some land area (possibly the same one). Certainly, each land area must appear in the trail. Note that at least two vertices of $M$ are neither the initial nor the terminal vertex of the trail. Let’s say that we start at land $A$ and end at land $A$.

Each of the land areas, except for the first and the last, is entered and exited every time it appears in the trail. This implies that all such land areas must have an even degree for a trail to exist.

Going back to the Königsberg bridge problem, we can see that it’s impossible to find a trail because all the vertices have an odd degree.

• The length of the Eulerian circuit/trail of a graph $G$ is equal to $m+1$, where $m$ is the size of $G$.

For undirected graphs:

• A graph $G$ is an Eulerian graph if and only if every vertex of $G$ has an even degree.
• A graph $G$ contains an Eulerian trail if and only if exactly two vertices of $G$ have an odd degree. Also, each trail of $G$ begins at one of these vertices and ends at the other.

For directed graphs:

• A graph $G$ is an Eulerian graph if and only if every vertex of $G$ has the same incoming and outgoing degree and is strongly connected.
• A graph $G$ contains an Eulerian trail if and only if for each vertex, the difference between its incoming and outgoing degrees is 0, except for two vertices, one with a difference of $-1$ (start) and one with a difference of $+1$ (end). If these two vertices are connected by an edge, then the graph is strongly connected.

Hierholzer’s algorithm

Let $C$ be a cycle in an Eulerian graph. Removing $E(C)$ from $G$ will create a subgraph that has an Eulerian trail.

1. Identify a circuit $C$ in $G$ and mark the edges of $C$.
2. If $C$ contains all the edges of $G$, then stop.
3. Otherwise, let $v_i$ be a node on $C$ that is incident with an unmarked edge $e_i$.
4. Build a circuit $D$ starting at node $v_i$ and using edge $e_1$, and mark the edges of $D$.
5. Join the circuit $D$ to $C$ by inserting the edges of $D$ into $C$ at position $v_1$, and then move to step 2.

Implementation notes

In the implementation, a source vertex $u$ is chosen to be arbitrary or to be one of the two odd-degree vertices. Then an edge $uv$ is marked as visited, and we move to vertex $v$. Next, an edge $vw$ is marked as visited. Eventually, we will get to a vertex $z$ that doesn’t have any unvisited edges. This means that there’s a circuit starting and ending at vertex $z$. Next, there might be a vertex $y$ in the circuit $z-z$ that has unvisited edges. If one is found, we know that there’s another circuit $y-y$. Both circuits $z-z$ and $y-y$ might have nested circuits themselves. When the $y-y$ circuit doesn’t have a vertex with unvisited edges, then the result is appended to the main circuit $z-z$, i.e., $u-v-\dots -z-y-y-z$.

// each edge is saved by id, helper to avoid the traversal
// of an edge many times
vector<bool> edge_used;
// the number of edges used in the adjacency list of the vertex `i`
vector<int> edge_pointer;
// the eulerian trail
vector<int> trail;
// the adjacency list representation of `g`, each element `g_{i,j}` is
// a tuple (to, id) which denotes an edge `(i, to)` with id `id`
vector<vector<pair<int, int> > > g;

void dfs(int v) {
  for (; edge_pointer[v] < g[v].size(); edge_pointer[v] += 1) {
    pair<int, int> &edge = g[v][edge_pointer[v]];
    if (edge_used[edge.second]) {
      // if the edge was already used analyze the next one
      continue;
    }
    // mark the edge
    edge_used[edge.second] = true;
    dfs(edge.first);
  }
  trail.push_back(v);
}

/**
 * Computes an euler trail if possible in an undirected graph `G`
 * whose `edges` are given as an input
 *
 * NOTE: The trail if it exists is saved on the global `trail`
 *
 * @param {int} n The order of the graph
 * @param {vector<pair<int, int> >} A collection of tuples
 * denoting the indexes of the vertices the edge `i` is incident to
 * @return {bool} True if the graph has an euler trail
 */
bool euler_trail_undirected(int n, vector<pair<int, int> > &edges) {
  int m = edges.size();
  g.assign(n, vector<pair<int, int> > ());
  edge_pointer.assign(n, 0);
  edge_used.assign(m, 0);
  vector<int> deg(n, 0);

  // build the adjacency list of the graph
  for (int i = 0; i < m; i += 1) {
    int u = edges[i].first;
    int v = edges[i].second;
    g[u].push_back({ v, i });
    g[v].push_back({ u, i });
    deg[u] += 1;
    deg[v] += 1;
  }

  // find an odd vertex
  int start = 0;
  int odd_degree_count = 0;
  for (int i = 0; i < n; i += 1) {
    if (deg[i] % 2 != 0) {
      ++odd_degree_count;
      start = i;
    }
  }

  if (odd_degree_count == 2 || odd_degree_count == 0) {
    dfs(start);
    return trail.size() == m + 1;
  }
  return false;
}


/**
 * Computes an euler trail if possible in an directed graph `G`
 * whose `edges` are given as an input
 *
 * NOTE: The trail if it exists is saved on the global `trail`
 *
 * @param {int} n The order of the graph
 * @param {vector<pair<int, int> >} A collection of tuples
 * denoting the indexes of the vertices the edge `i` is incident to
 * @return {bool} True if the graph has an euler trail
 */
bool euler_trail_directed(int n, vector<pair<int, int> > &edges) {
  int m = edges.size();
  g.assign(n, vector<pair<int, int> > ());
  edge_pointer.assign(n, 0);
  edge_used.assign(m, 0);
  vector<int> in_deg(n, 0), out_deg(n, 0);

  // build the adjacency list of the graph
  for (int i = 0; i < m; i += 1) {
    int u = edges[i].first;
    int v = edges[i].second;
    g[u].push_back({ v, i });
    out_deg[u] += 1;
    in_deg[v] += 1;
  }

  // find an odd vertex
  int start = 0;
  int odd_degree_count = 0;
  for (int i = 0; i < n; i += 1) {
    if (in_deg[i] - out_deg[i] != 0) {
      ++odd_degree_count;
      if (out_deg[i] > in_deg[i]) {
        start = i;
      }
    }
  }

  if (odd_degree_count == 2 || odd_degree_count == 0) {
    dfs(start);
    return trail.size() == m + 1;
  }
  return false;
}