Discrete Mathematics for Computer Science

342 CHAPTER 6 Graph Theory

Conditions Satisfied by Hamiltonian Graphs

1. A Hamiltonian graph cannot contain a vertex of degree zero or one.


2. If a vertex has degree two, then both edges incident to that vertex must be in every
   Hamiltonian cycle in the graph.


3. Every vertex in a Hamiltonian cycle must be at the end of two edges.


4. If a vertex has degree greater than two and two of its edges are chosen to be in
   a Hamiltonian cycle, then the other edges incident to the vertex can be removed
   from further consideration.


5. In constructing a Hamiltonian cycle edge by edge, an edge cannot be chosen that
   completes a cycle that does not include all the vertices of the graph.

The next two examples show how such observations can be used.

Example 5. Prove that neither of the following graphs is Hamiltonian:

b

6 5 4 f id

e

(a) (b)

Solution.

(a) By condition 3, vertex 2 must be an end to one of the following six pairs of edges:

i. (1, 2) and (2, 3)

ii. (1, 2) and (2, 4)

iii. (1, 2) and (2, 5)

iv. (2, 5) and (2, 3)

v. (2, 5) and (2, 4)

vi. (2, 3) and (2, 4)

The six cases are very similar, so we will just show the first case. Suppose a Hamilto-

nian cycle in the graph contains the edges (1, 2) and (2, 3). Edges (2, 5) and (2, 4) can

be removed from further consideration, since we have chosen (1, 2) and (2, 3) to be

the two edges incident to vertex 2 in a Hamiltonian cycle. We must then complete the

Hamiltonian cycle in the graph shown in Figure 6.11.

1 2 3

6 5 4

Figure 6.11 Remaining graph for Hamiltonian cycle construction.

Clearly, it is impossible to find any cycle in the graph shown. The remaining cases are

left as an exercise for the reader.