An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour, is a trail which starts and ends at the same
vertex. In other words, it is a graph cycle which
uses each graph edge exactly once. For technical reasons,
Eulerian cycles are mathematically easier to study than are Hamiltonian
cycles. An Eulerian cycle for the octahedral
graph is illustrated above.
As a generalization of the
Königsberg bridge problem, Euler showed (without proof) that a connected
graph has an Eulerian cycle iff it has no graph
vertices of odd degree.
Fleury's algorithm is an elegant, but inefficient, method of generating an Eulerian cycle. An Eulerian cycle of a graph may be found
in the Wolfram Language using [ FindEulerianCycle g].
Platonic solid possessing an Eulerian cycle is the octahedron, which has Schläfli
all other Platonic graphs have odd degree sequences. Similarly, the only Eulerian
Archimedean solids are the cuboctahedron,
rhombicosidodecahedron, and small rhombicuboctahedron.
See also Chinese Postman Problem
Explore with Wolfram|Alpha
References Bollobás, B. New York: Springer-Verlag, p. 12, 1979. Graph Theory: An Introductory Course. Gardner,
M. Chicago, IL: University
of Chicago Press, pp. 94-96, 1984. The
Sixth Book of Mathematical Games from Scientific American. Hierholzer, C. "Über
die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechnung zu
umfahren." Math. Ann. 6, 30-42, 1873. Lucas, E. Récréations
Mathématiques. Paris: Gauthier-Villars, 1891. Skiena, S. "Eulerian
Cycles." §5.3.3 in Reading,
MA: Addison-Wesley, pp. 192-196, 1990. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Referenced on Wolfram|Alpha Eulerian Cycle
Cite this as:
Weisstein, Eric W. "Eulerian Cycle." From
--A Wolfram Web Resource. MathWorld https://mathworld.wolfram.com/EulerianCycle.html