Eulerian Cycle

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 graph 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].

The only Platonic solid possessing an Eulerian cycle is the octahedron, which has Schläfli symbol ; all other Platonic graphs have odd degree sequences. Similarly, the only Eulerian Archimedean solids are the cuboctahedron, icosidodecahedron, small rhombicosidodecahedron, and small rhombicuboctahedron.

REFERENCES

Bollobás, B. Graph Theory: An Introductory Course. New York: Springer-Verlag, p. 12, 1979.

Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 94-96, 1984.

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 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 192-196, 1990.