Eulerian path Guide, Meaning , Facts, Information and Description
An Eulerian path (Eulerian trail, Euler walk) in a graph is a path that uses each edge precisely once. If such a path exists, the graph is called traversable.An Eulerian cycle (Eulerian circuit, Euler tour) in a graph is a cycle with uses each edge precisely once. If such a cycle exists, the graph is called Eulerian (also unicursal).
Note: 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. That is why it is best to use the terms Eulerian trail and Eulerian circuit to avoid any potential confusion.
The name is after a famous mathematician Leonhard Euler, who stated and solved the problem of Seven Bridges of Königsberg in 1736, which is the first formally discussed problem in graph theory. However, Euler's proof was lost for a long time, and Hierholzer rediscovered the result and first published a proof in 1873.
L. Euler showed that an Eulerian cycle exists if and only if all vertices in the graph are of even degree and all edges are contained in the same component. An Eulerian path exists, if and only if at most two vertices in the graph are of odd degree and all edges are contained in the same component.
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 (trail) or cycle (circuit) out of this graph by using Fleury's algorithm, which dated back to no later than 1921. We start with a vertex of odd degree— if the graph has none, then start with any vertex. Each time we move across an edge we delete it provided the remaining subgraph does not have more than one component containing an edge. Keep track of the sequence of edge deletions. At the end of the algorithm, we obtain an Eulerian path (trail) or Eulerian cycle (circuit) depending on whether the graph has two or no vertices of odd degree.
A directed graph version of Eulerian cycle (circuit) result and algorithm can be obtained in a similar fashion except that the even degree condition is replaced by an equal in- and out-degrees condition. Eulerian path (trail) can be treated likewise.