NIST

Euler cycle

(definition)

Definition: A path through a graph which starts and ends at the same vertex and includes every edge exactly once.

Also known as Eulerian path, Königsberg bridges problem.

Aggregate parent (I am a part of or used in ...)
Christofides algorithm.

See also Hamiltonian cycle, Chinese postman problem.

Note: "Euler" is pronounced "oil-er". A Hamiltonian cycle includes each vertex once; an Euler cycle includes each edge once.

Author: PEB

More information

examples and explanations (Java, C++, and Mathematica)

Historical Note
Euler defined the cycle to solve the puzzle of finding a path across every bridge of the German city of Königsberg exactly once.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 November 2020.
HTML page formatted Mon Nov 2 12:36:42 2020.

Cite this as:
Paul E. Black, "Euler cycle", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 2 November 2020. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/eulercycle.html