Eulerian path

The Königsberg Bridges graph. This graph is not Eulerian, therefore, a solution does not exist.

Every vertex of this graph has an even degree, therefore this is an Eulerian graph. Following the edges in alphabetical order gives an Eulerian circuit/cycle.

In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian trail which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. Mathematically the problem can be stated like this:

Given the graph on the right, is it possible to construct a path (or a cycle, i.e. a path starting and ending on the same vertex) which visits each edge exactly once?

Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated without proof that connected graphs with all vertices of even degree have an Eulerian circuit. The first complete proof of this latter claim was published in 1873 by Carl Hierholzer.

The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.

For the existence of Eulerian trails it is necessary that no more than two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. Sometimes a graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.

Definition

An Eulerian trail, Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. If such a path exists, the graph is called traversable or semi-eulerian.

An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses each edge exactly once. If such a cycle exists, the graph is called unicursal. While such graphs are Eulerian graphs, not every Eulerian graph possesses an Eulerian cycle.

For directed graphs path has to be replaced with directed path and cycle with directed cycle.

The definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as well.

Properties

• A connected undirected graph is Eulerian if and only if every graph vertex has an even degree, or exactly two vertices have an odd degree.
• An undirected graph is Eulerian if it is connected and can be decomposed into edge-disjoint cycles.
• If an undirected graph G is Eulerian then its line graph L(G) is Eulerian too.
• A directed graph is Eulerian if it is strongly connected and every vertex has equal in degree and out degree.
• A directed graph is Eulerian if it is strongly connected and can be decomposed into edge-disjoint directed cycles.
• An Eulerian trail exists in a directed graph if and only if the graph's underlying undirected graph is connected, at most one vertex has out degree-in degree=1, at most one vertex has in degree-out degree=1 and every other vertex has equal in degree and out degree.
• An undirected graph is traversable if it is connected and at most two vertices in the graph are of odd degree.

Constructing Eulerian trails and circuits

Consider a graph known to have all edges in the same component and at most two vertices of odd degree. We can construct an Eulerian trail out of this graph by using Fleury's algorithm, which dates to 1883. We start with a vertex of odd degree—if the graph has none, then start with any vertex. At each step we move across an edge whose deletion would not disconnect the graph, unless we have no choice, then we delete that edge. At the end of the algorithm there are no edges left, and the sequence of edges we moved across forms an Eulerian cycle if the graph has no vertices of odd degree; or an Eulerian trail if there are exactly two vertices of odd degree.

Counting Eulerian circuits

Complexity issues

The number of Eulerian circuits in digraphs can be calculated using the so called BEST theorem, named after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte. The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted arborescences. The latter can be computed as a determinant, by the matrix tree theorem, giving a polynomial time algorithm.

BEST theorem is first stated in this form in a "note added in proof" to the Aardenne-Ehrenfest and de Bruijn paper (1951). The original proof was bijective and generalized the de Bruijn sequences. It is a variation on an earlier result by Smith and Tutte (1941).

Counting the number of Eulerian circuits on undirected graphs is much more difficult. This problem is known to be #P-complete. In a positive direction, a Markov chain Monte Carlo approach, via the Kotzig transformations (introduced by Anton Kotzig in 1968) is believed to give a sharp approximation for the number Eulerian circuits in a graph.

Special cases

The asymptotic formula for the number of Eulerian circuits in the complete graphs was determined by McKay and Robinson (1995):

$ec(K_{n})=2^{(n+1)/2}\pi ^{1/2}e^{-n^{2}/2+11/12}n^{(n-2)(n+1)/2}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.$

A similar formula was later obtained by M.I. Isaev (2009) for complete bipartite graphs:

$ec(K_{n,n})=(n/2-1)!^{2n}2^{n^{2}-n+1/2}\pi ^{-n+1/2}n^{n-1}{\bigl (}1+O(n^{-1/2+\epsilon }){\bigr )}.$

Applications

Eulerian trails are being used in bioinformatics to reconstruct the DNA sequence from its fragments.

See also

• The handshaking lemma, proven by Euler in his original paper, showing that any undirected connected graph has an even number of odd-degree vertices
• Hamiltonian path - a path that visits each vertex exactly once.

References

• Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128-140.
• Hierholzer, C., "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Mathematische Annalen 6 (1873), 30-32.
• Lucas, E., Récréations Mathématiques IV, Paris, 1921.
• Fleury, "Deux problemes de geometrie de situation", Journal de mathematiques elementaires (1883), 257-261.
• T. van Aardenne-Ehrenfest and N. G. de Bruijn, Circuits and trees in oriented linear graphs, Simon Stevin, 28 (1951), 203-217.
• W. T. Tutte and C. A. B. Smith, On Unicursal Paths in a Network of Degree 4. Amer. Math. Monthly, 48 (1941), 233-237.

External links

• Discussion of early mentions of Fleury's algorithm