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 path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path 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?

Graphs which allow the construction of so called Eulerian circuits are called Eulerian graphs. Euler observed that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and that for an Eulerian path either all, or all but two (i.e., the two endpoint) vertices have an even degree; this means the Königsberg graph is not Eulerian. Sometimes a graph that has an Eulerian path, but not an Eulerian circuit (in other words, it is an open path, and does not start and end at the same vertex) is called semi-Eulerian.

Carl Hierholzer published the first complete characterization of Eulerian graphs in 1873, by proving that in fact the Eulerian graphs are exactly the graphs which are connected and where every vertex has an even degree.

Definition

An Eulerian path, 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 Eulerian or unicursal. The cycle starts and ends at the same vertex.

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

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

Notes

Some people reserve the terms path and cycle to mean non-self-intersecting path and cycle. A (potentially) self-intersecting path is known as a trail or an open walk; and a (potentially) self-intersecting cycle, a circuit or a closed walk. This ambiguity can be avoided by using the terms Eulerian trail and Eulerian circuit when self-intersection is allowed.

Properties

• A connected undirected graph is Eulerian if and only if every graph vertex has an even 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 iff it is strongly connected and every vertex has equal in degree and out degree.
• A directed graph is Eulerian iff it is strongly connected and can be decomposed into edge-disjoint directed cycles.
• An undirected graph is traversable if it is connected and at most two vertices in the graph are of odd degree.

Constructing Eulerian paths and cycles

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 path (not a cycle) 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 path if there are two vertices of odd degree.

The definition of a Hamiltonian path is very similar (a Hamiltonian path visits every vertex exactly once, while an Eulerian path visits every edge exactly once). In practice, however, it is much more difficult to construct a Hamiltonian path or determine whether a graph is Hamiltonian, as that problem is NP-complete.

Constructing Eulerian graphs for a given partition of p

For a frequency partition p = f₁ + f₂ + ... + f_k of an integer p > 1, its graphic degree sequence is denoted as ((d₁)^f₁,(d₂)^f₂, (d₃)^f₃, ..., (d_k) ^f_k) where degrees d_i's are different and f_i ≥ f_j for i < j. Bhat-Nayak et al. (1979) showed that a partition of p with k parts, k ≤ integral part of (p − 1) / 2 is a frequency partition ^[1] of an Eulerian graph and conversley. The graphic degree sequences of the partitions are:

• For p = , ...(2m + 2)^f₃,(2m)^f₁,(2m - 2)^f₂, ... , example, for 12 = 5 + 4 + 3, the Eulerian degree sequence is 8³,6⁵,4⁴.

• For p = , ...(2m + 2)^f₂,(2m)^f₁,(2m - 2)^f₃, ... , example, for 13 = 6 + 4 + 3, the Eulerian degree sequence is 8⁴,6⁶,4³.

• For p = , ...(2m + 2)^f₂,(2m)^f₁,(2m - 2)^f₃, ... , example, for 14 = 6 + 5 + 3, the Eulerian degree sequence is 8⁵,6⁶,4³.

• For p = , ...(2m + 4)^f₃,(2m + 2)^f₁,(2m)^f₂, ... , example, for 15 = 6 + 5 + 4, the Eulerian degree sequence is 10⁴,8⁶,6⁵.

Counting Eulerian circuits

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.

Given an Eulerian digraph G := (V, E), the number of non-equivalent Eulerian circuits in the graph is

or equivalently

with C any cofactor of the Laplacian matrix of G.

Counting the number of Eulerian circuits on undirected graphs is much more difficult; it is known to be #P-complete.^[2]

The asymptotic number of Eulerian Circuits in the complete graph was determined by McKay & Robinson.

Applications

Eulerian paths are being used in bioinformatics to reconstruct the DNA sequence from its fragments.^[3]

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

Notes

1. ^ Vasanti N. Bhat-Nayak, Ranjan N. Naik and S. B. Rao, Characterization of Frequency Partitions of Eulerian Graphs – ISI Lecture Notes No. 4 (Edited A R Rao) Proc. Symposium on graph Theory, Published by The MacMillan comp. of India Ltd 1979. Also in Lecture Notes in Mathematics, Combinatorics and Graph Theory, Springer-Verlag, New York, Vol. 885 (1980), p 500.
2. ^ Brightwell and Winkler, "Note on Counting Eulerian Circuits", 2004.
3. ^ Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). "An Eulerian path approach to DNA fragment assembly". Proceedings of the National Academy of Sciences of the United States of America 98 (17): 9748-9753. doi:10.1073/pnas.171285098. http://www.pnas.org/content/98/17/9748.long. 

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.

External links

Wikimedia Commons has media related to: Eulerian paths

• Discussion of early mentions of Fleury's algorithm
• McKay & Robinson. Asymptotic enumeration of eulerian circuits in the complete graph