Section outline

  • In graph theory, two fundamental types of traversal problems are the Hamiltonian and Eulerian problems. Both deal with finding specific paths or cycles that visit the vertices or edges of a graph under certain conditions.
    A Hamiltonian cycle is a closed path that visits each vertex of the graph exactly once before returning to the starting vertex. Determining whether such a cycle exists is a central and challenging question in graph theory, often associated with complex combinatorial structures.

    In this chapter, we present the main definitions and discuss both necessary and sufficient conditions for the existence of Hamiltonian paths and cycles.
    On the other hand, an Eulerian cycle is a closed path that traverses every edge of the graph exactly once. The study of Eulerian graphs dates back to the 18th century with Euler’s solution to the famous Königsberg bridge problem. We will recall the definitions, establish the necessary and sufficient conditions for the existence of an Eulerian cycle, and describe a simple local algorithm for its
    construction.

    Finally, the chapter concludes with a discussion of the relations between Hamiltonian and Eulerian problems, highlighting the similarities and fundamental differences between these two classic graph-theoretic concepts.