Page 720 - Discrete Mathematics and Its Applications

10.5 Euler and Hamilton Paths 699

(a) (b)
FIGURE 9 A Solution to
FIGURE 8 Hamilton’s “A Voyage Round the the “A Voyage Round the
World” Puzzle. World” Puzzle.

Because the author cannot supply each reader with a wooden solid with pegs and string, we
will consider the equivalent question: Is there a circuit in the graph shown in Figure 8(b) that
passes through each vertex exactly once? This solves the puzzle because this graph is isomorphic
to the graph consisting of the vertices and edges of the dodecahedron. A solution of Hamilton’s
puzzle is shown in Figure 9.

EXAMPLE 5 Which of the simple graphs in Figure 10 have a Hamilton circuit or, if not, a Hamilton path?

Solution: G 1 has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in G 2 (this can
be seen by noting that any circuit containing every vertex must contain the edge {a, b} twice),
but G 2 does have a Hamilton path, namely, a, b, c, d. G 3 has neither a Hamilton circuit nor a
Hamilton path, because any path containing all vertices must contain one of the edges {a, b},
{e, f }, and {c, d} more than once. ▲

a b a b a b g

e c
d c d c e f
G G
G 1 2 3
d
FIGURE 10 Three Simple Graphs.

CONDITIONS FORTHE EXISTENCE OF HAMILTON CIRCUITS Is there a simple way
to determine whether a graph has a Hamilton circuit or path? At first, it might seem that there
should be an easy way to determine this, because there is a simple way to answer the similar
question of whether a graph has an Euler circuit. Surprisingly, there are no known simple
necessary and sufficient criteria for the existence of Hamilton circuits. However, many theorems
are known that give sufficient conditions for the existence of Hamilton circuits. Also, certain
properties can be used to show that a graph has no Hamilton circuit. For instance, a graph with a
vertex of degree one cannot have a Hamilton circuit, because in a Hamilton circuit, each vertex
is incident with two edges in the circuit. Moreover, if a vertex in the graph has degree two, then
both edges that are incident with this vertex must be part of any Hamilton circuit. Also, note
that when a Hamilton circuit is being constructed and this circuit has passed through a vertex,
then all remaining edges incident with this vertex, other than the two used in the circuit, can be
removed from consideration. Furthermore, a Hamilton circuit cannot contain a smaller circuit
within it.