SKEDSOFT

Introduction: A simple path in a graphGthat passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph G that passes through every vertex exactly once is called a Hamilton circuit. That is, the simple path x0, x1, . . . , xn−1, xn in the graph G = (V ,E) is a Hamilton path if V = {x0, x1, . . . , xn−1, xn} and xi = xj for 0 ≤ i < j ≤ n, and the simple circuit x0, x1, . . . , xn−1, xn, x0 (with n > 0) is a Hamilton circuit if x0, x1, . . . , xn−1, xn is a Hamilton path.

This terminology comes from a game, called the Icosian puzzle, invented in 1857 by the Irish mathematician Sir William Rowan Hamilton. It consisted of a wooden dodecahedron a polyhedron with 12 regular pentagons as faces, as shown in Figure 8(a)], with a peg at each vertex of the dodecahedron, and string. The 20 vertices of the dodecahedron were labeled with different cities in the world. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the first city. The circuit traveled was marked off using the string and pegs.

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 1 Which of the simple graphs in Figure 10 have a Hamilton circuit or, if not, a Hamilton path?
Solution: G1 has a Hamilton circuit: a, b, c, d, e, a. There is no Hamilton circuit in G2 (this can be seen by noting that any circuit containing every vertex must contain the edge {a, b} twice), but G2 does have a Hamilton path, namely, a, b, c, d. G3 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.

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.

EXAMPLE 2 Show that neither graph displayed in Figure 11 has a Hamilton circuit.
Solution: There is no Hamilton circuit in G because G has a vertex of degree one, namely, e. Now consider H. Because the degrees of the vertices a, b, d, and e are all two, every edge incident with these vertices must be part of any Hamilton circuit. It is now easy to see that no Hamilton circuit can exist in H, for any Hamilton circuit would have to contain four edges incident with c, which is impossible.