Hamiltonian cycles and paths are graph traversals that visit every vertex exactly once. Cycles return to the start, while paths can have different endpoints. These concepts, introduced by William Hamilton, are crucial in graph theory and optimization problems.

Understanding Hamiltonian graphs involves key theorems like Dirac's and Ore's, which provide conditions for their existence. Identifying these structures uses techniques from brute force to heuristic methods, with applications in the famous Traveling Salesman Problem.

Hamiltonian Cycles and Paths Fundamentals

Definition of Hamiltonian cycles and paths

• Hamiltonian path traverses every vertex in a graph exactly once without revisiting allows different start and end vertices (Königsberg Bridge problem)
• Hamiltonian cycle visits every vertex in a graph exactly once returns to starting vertex forms closed loop (Dodecahedron graph)
• William Rowan Hamilton introduced these concepts while studying dodecahedron graph in 1800s led to development of Icosian game

Hamiltonian cycles vs paths

• End points differ Hamiltonian path can have different start and end vertices while cycle must return to start
• Edge count Hamiltonian path uses $n-1$ edges in n-vertex graph cycle uses n edges
• Closure property Hamiltonian path forms open walk cycle creates closed walk
• Flexibility paths offer more options for traversal cycles more restrictive due to return requirement

Properties of Hamiltonian graphs

• Dirac's Theorem ensures Hamiltonian cycle if minimum vertex degree $\geq n/2$ (Complete graph $K_5$)
• Ore's Theorem guarantees Hamiltonian cycle if degree sum of non-adjacent vertices $\geq n$ (Petersen graph)
• Complete graphs $K_n$ always contain Hamiltonian cycles for $n \geq 3$ (Triangle, Square, Pentagon)
• Bipartite graphs can have Hamiltonian cycles only with equal-sized partite sets (Hypercube graph)
• All Platonic solids possess Hamiltonian cycles due to symmetry and connectivity (Cube, Tetrahedron)

Techniques for identifying Hamiltonian graphs

• Bondy-Chvátal Theorem uses graph closure by adding edges based on degree sum
• Pósa's Theorem provides sufficient condition for Hamiltonian paths based on vertex degree distribution
• Traveling Salesman Problem closely related to finding optimal Hamiltonian cycles in weighted graphs
• Brute force approach checks all vertex permutations becomes impractical for large graphs
• Backtracking algorithms build and explore potential solutions systematically (Depth-First Search)
• Heuristic methods approximate solutions:
  1. Nearest neighbor algorithm greedily selects closest unvisited vertex
  2. Christofides algorithm guarantees solution within 1.5 times optimal for metric TSP