What is a Euler or Eulerian tour?

• Definition
• Conditions
• Observations
• Discussions

Reading time: 10 minutes

An Euler tour or Eulerian tour in an undirected graph is a tour/ path that traverses each edge of the graph exactly once. Graphs that have an Euler tour are called Eulerian graphs.

Necessary and sufficient conditions

An undirected graph has a closed Euler tour if and only if it is connected and each vertex has an even degree.

An undirected graph has an open Euler tour (Euler path) if it is connected, and each vertex, except for exactly two vertices, has an even degree. The two vertices of odd degree have to be the endpoints of the tour.

A directed graph has a closed Euler tour if and only if it is strongly connected and the in-degree of each vertex is equal to its out-degree.

Similarly, a directed graph has an open Euler tour (Euler path) if and only if for each vertex the difference between its in-degree and out-degree is 0, except for two vertices, where one has difference +1 (the start of the tour) and the other has difference -1 (the end of the tour) and, if you add an edge from the end to the start, the graph is strongly connected.

Observations

• If C is any cycle in a Eulerian graph, then after removing the edges of C, the remaining connected components will also be Eulerian graphs.

• Use Depth First Search recursively to find eulerian path in a graph.

• In an undirected eulerian graph, each vertex, except for exactly two vertices, has an even degree.

• In a directed eulerian graph, the difference between its in-degree and out-degree is 0, except for two vertices, where one has difference +1 (the start of the tour) and the other has difference -1 (the end of the tour).

• Adding an edge from end to start of a tour in a direct graph results in a strongly connected graph.