Eulerian path

They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736.

The problem can be stated mathematically like this: 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 definition and properties of Eulerian trails, cycles and graphs are valid for multigraphs as well.

At the end of the algorithm there are no edges left, and the sequence from which the edges were chosen 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.

Hierholzer's 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm: By using a data structure such as a doubly linked list to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes linear time,

Because it is only possible to get stuck when the deque represents a closed tour, one should rotate the deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for.

(intuitively, any "bad" edges are moved to the head, while fresh edges are added to the tail) 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 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).

Counting the number of Eulerian circuits on undirected graphs is much more difficult.

[10] 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 of Eulerian circuits in a graph, though as yet there is no proof of this fact (even for graphs of bounded degree).

Isaev (2009) for complete bipartite graphs:[12] Eulerian trails are used in bioinformatics to reconstruct the DNA sequence from its fragments.

[13] They are also used in CMOS circuit design to find an optimal logic gate ordering.

It is not sufficient for the existence of such a trail that the graph be connected and that all vertex degrees be even; for instance, the infinite Cayley graph shown, with all vertex degrees equal to four, has no Eulerian line.

The infinite graphs that contain Eulerian lines were characterized by Erdős, Grünwald & Weiszfeld (1936).

The following result was proved by Veblen in 1912: An undirected connected graph is Eulerian if and only if it is the disjoint union of some cycles.

[20]Hierholzer developed a linear time algorithm for constructing an Eulerian tour in an undirected graph.

That is, a directed graph is Eulerian if and only if it is connected and the in-degree and out-degree are equal at each vertex.

Hierholzer's linear time algorithm for constructing an Eulerian tour is also applicable to directed graphs.

[20] Ford and Fulkerson proved in 1962 in their book Flows in Networks a necessary and sufficient condition for a graph to be Eulerian, viz., that every vertex must be even and satisfy the balance condition, i.e. for every subset of vertices S, the difference between the number of arcs leaving S and entering S must be less than or equal to the number of edges incident with S.[20]

The process of checking if a mixed graph is Eulerian is harder than checking if an undirected or directed graph is Eulerian because the balanced set condition concerns every possible subset of vertices.

Multigraphs of both Königsberg Bridges and Five room puzzles have more than two odd vertices (in orange), thus are not Eulerian and hence the puzzles have no solutions.
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.
Using Eulerian trails to solve puzzles involving drawing a shape with a continuous stroke:
  1. As the Haus vom Nikolaus puzzle has two odd-degree vertices (orange), the trail must start at one and end at the other.
  2. A variant with four odd-degree vertices has no solution.
  3. If there are no odd-degree vertices, the trail can start anywhere and forms an Eulerian cycle.
  4. Loose ends are considered vertices of degree 1.
  5. The graph must also be connected.
Orthographic projections and Schlegel diagrams with Hamiltonian cycles of the vertices of the five platonic solids – only the octahedron has an Eulerian path or cycle, by extending its path with the dotted one
An infinite graph with all vertex degrees equal to four but with no Eulerian line
A directed graph with all even degrees that is not Eulerian, serving as a counterexample to the statement that a sufficient condition for a directed graph to be Eulerian is that it has all even degrees
A directed graph with all even degrees that is not Eulerian, serving as a counterexample to the statement that a sufficient condition for a directed graph to be Eulerian is that it has all even degrees
This mixed graph is Eulerian. The graph is even but not symmetric which proves that evenness and symmetricness are not necessary and sufficient conditions for a mixed graph to be Eulerian.
This mixed graph is Eulerian. The graph is even but not symmetric which proves that evenness and symmetricness are not necessary and sufficient conditions for a mixed graph to be Eulerian.
An even mixed graph that violates the balanced set condition and is therefore not Eulerian.
An even mixed graph that violates the balanced set condition and is therefore not Eulerian.
An even mixed graph that satisfies the balanced set condition and is therefore an Eulerian mixed graph.
An even mixed graph that satisfies the balanced set condition and is therefore an Eulerian mixed graph.