Eulerian path
From Academic Kids

Konigsburg_graph.png
In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. 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 cycles are called Eulerian graphs. Euler observed that a necessary condition for the existence of Eulerian cycles is that all vertices in the graph have an even degree, and that for an Eulerian path either all, or all but two, vertices have an even degree; this means the Königsberg graph is not 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.
Contents 
Definition
An Eulerian path, Eulerian trail or Euler walk in a undirected graph is a path that uses each edge exactly once. If such a path exists, the graph is called traversable.
An Eulerian cycle, Eulerian circuit or Euler tour in a undirected graph is a cycle with uses each edge exactly once. If such a cycle exists, the graph is called Eulerian or unicursal.
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 nonselfintersecting path and cycle. A (potentially) selfintersecting path is known as a trail or an open walk; and a (potentially) selfintersecting 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.
Examples
 Every cycle graph is Eulerian and every dicycle graph is Eulerian.
Properties
 An undirected graph is Eulerian iff it is connected and every vertex has an even degree
 An undirected graph is Eulerian iff it can be constructed using edge disjunct cycle graphs.
 An undirected graph is traversable iff it is connected and at most two vertices in the graph are of odd degree.
 If an undirected graph G is Eulerian then its line graph L(G) is Eulerian too.
 A directed graph is Eulerian iff it is diconnected and every vertex has equal in degree and out degree.
 A directed graph is Eulerian iff it can be constructed using arc disjunct dicycle graphs.
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 or cycle out of this graph by using Fleury's algorithm, which dates back to no later than 1921. 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 does not result in more than one component containing edges (such an edge can be proved to exist), 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 path or Eulerian cycle depending on whether the graph has two or no vertices of odd degree.
A directed graph version of the Eulerian cycle algorithm can be obtained in a similar fashion, except that the even degree condition is replaced by an equal in and outdegrees condition. The Eulerian path can be treated likewise.
Counting Eulerian circuits in digraphs
The number of Eulerian circuits in digraphs can be calculated using the so called BESTtheorem, named after de Bruijn, van AardenneEhrenfest, Smith and Tutte.
Given a Eulerian digraph G := (V, E), the number of nonequivalent Eulerian circuits in the graph is
 <math>C \prod_{v \in V}(\deg^+(v)1)!<math>
or equivalently
 <math>C \prod_{v \in V}(\deg^(v)1)!<math>
with C any cofactor of the Laplacian matrix of G.
See also
External links
 http://math.dartmouth.edu/~euler/pages/E053.html : Euler Archive's page containing some information and (public domain) scan of Euler's paper as mentioned in References below.
References
 Euler, L., "Solutio problematis ad geometriam situs pertinentis", Comment. Academiae Sci. I. Petropolitanae 8 (1736), 128140.
 Hierholzer, C., "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren", Mathematische Annalen 6 (1873), 3032.
 Lucas, E., Récréations Mathématiques IV, Paris, 1921.de:Eulerkreisproblem