344 CHAPTER 6 Graph Theory
Now, the second edges incident to vertices 2 and 5 must be one of the following four
pairs of edges:
(i) (2, 7) and (5, 10)
(ii) (2, 7) and (5, 4) or, symmetrically, (5, 10) and (2, 3)
(iii) (2, 3) and (5, 4)
If edges (2, 7) and (5, 10) are chosen, the edges (5, 4) and (2, 3) can be deleted by
condition 4. The edges (4, 9), (4, 3) (Case (i)) and (3, 8) must now be included in the
Hamiltonian cycle by condition 2. In Case ii, the choice of (2, 7) and (5, 4) will allow
edges (2, 3), (4, 9), and (5, 10) to be deleted by condition 4. The edges (3, 4) and (3,
8) must now be included in the Hamiltonian cycle by condition 2. Finally, in Case iii,
the choice of edges (2, 3) and (5, 4) will allow edges (5, 10) and (2, 7) to be deleted by
condition 4. The edge (3, 4) can be deleted by condition 5. The edges (4, 9) and (3, 8)
must now be included in the Hamiltonian cycle by condition 2. The graphs remaining
in which Hamiltonian cycles might be completed are shown in Figure 6.13.1 116 6 6
5 2 5 0 7 2 5 10 7 2
107 27(^99 8 9 8)
4 3 4 3 4 3
i. ii. iii.
Figure 6.13 Graphs for finishing a Hamiltonian cycle, a. Case i. b. Case ii. c. Case iii.
In each of these graphs, a choice of a second edge incident to vertex 8 will lead to a
violation of condition 5.
Case ii: This proof is left as an exercise for the reader.
(b) By symmetry in the graph, we need only show the result for the subgraphs formed
by deleting one of the outer vertices and one of the inner vertices. Figure 6.14 shows
Hamiltonian cycles in the resulting graphs.
5 10 7 2 5 102
(^9 8)
(a) (b)
Figure 6.14 Hamiltonian cycles in vertex-deleted subgraphs. a. Inner vertex deleted.
b. Outer vertex deleted. 0