Eulerian Tour in Directed and Undirected Graphs¶

Necessary and Sufficient Condition¶

The following mathematical conditions illustrate fundamental requirements in graph theory:

If a simple graph of order \(n \geq 3\) satisfies either of these conditions, it is Hamiltonian. The first condition corresponds to Dirac's theorem, while the second aligns with Ore's theorem. Both guarantee the existence of a Hamiltonian cycle under specified degree constraints.

Another formulation of these principles is:

\begin{align*}
    \text{Necessary condition: } & \delta(G) \geq \frac{k}{2} \\
    \text{Sufficient condition: } & \forall u,v \in V(G), uv \notin E(G) \Rightarrow \deg(u) + \deg(v) \geq k
\end{align*}

First, assume the graph in question is an undirected graph. Now we examine the necessary and sufficient conditions for the existence of an Eulerian tour. First, remove the isolated vertices of the graph. Now the necessary and sufficient conditions are:

• 1. The graph must be connected.

• 2. The degree of every vertex must be even.

First, we prove that the above two conditions are necessary.

Condition (a) is clearly necessary because if two edges belong to different connected components, a trail cannot simultaneously include both of them.

To prove the necessity of condition (b), note that whenever we enter a vertex through an edge, we must immediately exit it (note the exception for the starting vertex). Therefore, the number of edges adjacent to each vertex must be a multiple of 2.

Now we prove that the above two conditions are sufficient. For this, we use induction on the number of edges.

First, assume we have a closed trail starting from vertex \(start\) and returning to the same vertex: \(a_1 = start, a_2, ..., a_k = start\) which does not necessarily include all edges.

Now remove the edges of this trail from the graph. The graph decomposes into several connected components. Assign to each component the smallest index \(i\) such that \(a_i\) belongs to that component.

Now begin traversing the removed trail. Whenever we reach vertex \(a_i\), recursively construct and traverse the Eulerian tour of the component assigned to index \(i\).

Ultimately, the trail we have traversed will be the Eulerian tour of our graph!

Only one part of the proof remains. Why could we assume the existence of a closed trail containing \(start\)?

It suffices to start from \(start\) and at each step, if we are at vertex \(u\) where \(u \neq start\), traverse an adjacent edge of \(u\) that has not been traversed before, and continue this until we return to \(start\).

Why does such an edge exist? Because when we reach vertex \(u\), we have entered it an odd number of times and exited it an even number of times. Thus, the number of edges already traversed is odd, and by assumption, the degree of every vertex is even. Therefore, there must exist an edge that has not been traversed yet!

 1class Graph:
 2    def __init__(self, num_vertices):
 3        self.num_vertices = num_vertices
 4        # سازنده کلاس گراف
 5        self.adj = [[] for _ in range(num_vertices)]
 6
 7    def add_edge(self, u, v):
 8        # اضافه کردن یال به گراف جهت دار
 9        self.adj[u].append(v)
10        # self.adj[v].append(u)  # حذف کامنت برای گراف بی‌جهت

Implementation¶

First, we store the graph using an adjacency list. In the add_edge function (written here for a directed graph), two vertices are given as input and the function creates an edge between them (directed or undirected).

Note that the difference in code for finding Eulerian tours between directed and undirected graphs lies solely in the add_edge function.

const int max_edges = 1010, max_vertices = 1010;

int edge_counter = 1;

int to[max_edges], next[max_edges], top[max_edges];
bool used[max_edges];

void add_edge(int a, int b){
      to[edge_counter] = b;
      next[edge_counter] = top[a];
      top[a] = edge_counter;
      edge_counter++;
}

vector<int> ans;

void build(int start){
      while(top[start] != 0 && used[top[start]])
              top[start] = next[top[start]];
      if(top[start] == 0)
              return;
      vector <int> tmp;
      int u = start;

      do{
              while(top[u] != 0 && used[top[u]])
                      top[u] = next[top[u]];
              assert(top[u] == 0); // agar shart bargharar bashad graph euleri nist.
              used[top[u]] = 1;
              tmp.push_back(top[u]);
              u = to[top[u]];
      }while(start != u);

      u = start;
      for(int id : tmp){
              build(u);
              ans.push_back(id);
              u = to[id];
      }
}

int main(){

       // Take the graph as input and call add_edge for each edge
       // Call the build function
       // Now the order of edges is stored in the ans vector
}

What if the start and end vertices are not the same?¶

Suppose you want to find a trail that starts at vertex \(a\) and ends at vertex \(b\), covering all edges, with \(a \neq b\).

To convert this new problem into an Euler tour problem, it is sufficient to add an edge between \(a\) and \(b\). (If the graph is directed, add the edge from \(b\) to \(a\)).

Now, if we assume that we traverse the new edge first (in an Euler tour, it does not matter which edge we start with), the remaining trail is exactly what we were looking for. (Why?) Thus, we have successfully converted this problem into an Euler tour problem.