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 it and that it begins and ends in 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 in 4 land areas, to travel between these areas 7 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 $L$ lands but the first and the last are entered and exited every time they appear in the trail, this implies that all $L$ lands 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 even degree
• A graph $G$ contains an Eulerian trail if and only if exactly 2 vertices of $G$ have 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 degree and outgoing degree values and it’s strongly connected
• A graph $G$ contains an Eulerian trail if and only if for each vertex the difference between its incoming degrees and outgoing degrees is 0 except for 2 vertices whose difference is $-1$ (start) and $+1$ (end), if those edges 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 which has an Eulerian trail

1. identify a circuit $C$ in $G$, 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$, mark the edges of $D$
5. join the circuit $D$ to $C$ by inserting the edges of $D$ into $C$ at position $v_1$, move to step 2

Implementation notes

In the implementation a source vertex $u$ is chosen to be arbitrary or to be the one of the two odd degree vertices, then an edge $uv$ is marked as visited, then we move to the vertex $v$, next an edge $vw$ is marked as visited, eventually we will get to a vertex $z$ that doesn’t have unvisited edges, this means that there’s a circuit starting at vertex $z$ and ending at vertex $z$, next there might be one vertex $y$ in the circuit $z-z$ that has unvisited edges, if one is found we know that there’s other 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-\ldots-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;
}