SECTION 2.2 Elementary Graph Theory 117
- Does the graph to the right have an
Eulerian circuit? If so, find it.
2.2.2 Hamiltonian cycles and optimization
In the previous subsection we were largely concerned with the problem
of moving around a graph in such a way that each edge is traversed
exactly once. The present subsection is concerned with the “dual”
problem, namely that of moving around a graph in such a way that
each vertex is visited exactly once. Such a walk is called aHamil-
tonian path. If we return to the original vertex, the walk is called
a Hamiltonian cycle. The following figure depicts a graph and a
Hamiltonian cycle in the graph:
Curiously, unlike the question of the existence of Eulerian circuits,
there is no definitive simple criterion for the existence of Hamiltonian
cycles. Known results typically involve a lower bound on the degree of
each vertex.^29 See the exercises below for a few additional examples.
(^29) For example, a 1952 theorem of Paul Dirac says that a graph withnvertices has a Hamiltonian
cycle provided that each vertex has degree≥n/2. /Oystein Ore generalized this result to graphs
(withn≥3 vertices) such that for each pair of non-adjacent vertices the sum of their degrees is≥n.