47218 Hamilton Cyclesperson sticks pins in any five consecutive vertices and the other is required to comlottlformed to a spanning cycle (see Biggs et al. (1986) or Hamilton(1931). Hamilton was prompted to consider such cycles in his early investigationsinto group theory, the three edges incident to a vertex corresponding to threegenerators of a groupA graph is traceable if it contains a Hamilton path, and hamiltonian if it contains a Hamilton cycle. The dodecahedron is hamiltonian; a Hamilton cycle isindicated inFigure18.la.On the other hand,the Herschel graphof Figure18.1bis nonhamiltonian, because it is bipartite and has an odd number of vertices. Thisgraph is, however, traceable(a)(b)Fig. 18.1. Hamiltonian and nonhanmiltonian graphs: (a) the dodecahedron, (b) the Herschel graphTOUGH GRAPHSAs we saw in Section 8.3, the problem of deciding whether a given graph is hamiltonian is NP-complete. It is therefore natural to look for reasonable necessarysufficient conditions for the existence of Hamilton cycles. The following simplenecessary condition turns out to be surprisingly useful.Theorem 18.1 Let S be a set of vertices of a hamiltonian graph G. Then(18.1)c(G - S) ≤ISIMoreover, if equality holds in (18.1), then each of the [S] components of G -2tracableandeeryHamiltoncyceGincludsHamitonpathiachfthcomponents.Proof Let C be a Hamilton cycle of G. Then C - S clearly has at most [SlOnents. But this implies that G- S also has at most Js] components, becauseC is a spanning subgraph of G.472 18 Hamilton Cycles person sticks pins in any five consecutive vertices and the other is required to com￾plete the path so formed to a spanning cycle (see Biggs et al. (1986) or Hamilton (1931)). Hamilton was prompted to consider such cycles in his early investigations into group theory, the three edges incident to a vertex corresponding to three generators of a group. A graph is traceable if it contains a Hamilton path, and hamiltonian if it con￾tains a Hamilton cycle. The dodecahedron is hamiltonian; a Hamilton cycle is indicated in Figure 18.1a. On the other hand, the Herschel graph of Figure 18.1b is nonhamiltonian, because it is bipartite and has an odd number of vertices. This graph is, however, traceable. (a) (b) Fig. 18.1. Hamiltonian and nonhamiltonian graphs: (a) the dodecahedron, (b) the Her￾schel graph Tough Graphs As we saw in Section 8.3, the problem of deciding whether a given graph is hamil￾tonian is N P-complete. It is therefore natural to look for reasonable necessary or sufficient conditions for the existence of Hamilton cycles. The following simple necessary condition turns out to be surprisingly useful. Theorem 18.1 Let S be a set of vertices of a hamiltonian graph G. Then c(G − S) ≤ |S| (18.1) Moreover, if equality holds in (18.1), then each of the |S| components of G − S is traceable, and every Hamilton cycle of G includes a Hamilton path in each of these components. Proof Let C be a Hamilton cycle of G. Then C − S clearly has at most |S| components. But this implies that G−S also has at most |S| components, because C is a spanning subgraph of G