18.1 Hamiltonian and Nonhamiltonian Graphs473If G - S has exactly [SI cponents, C - S also has exactly [S| componenand the components of C- S are spanning subgraphs of the components of G- SIn other words, C includes a Hamilton path in each component of G - S.口A graph G is called tough if (18.1) holds for every nonempty proper subset Sof V.By Theorem 18.1, a graph which is not tough cannot behamiltonian.As anillustration, consider the graph G of Figure 18.2a. This graph has nine vertices.On deleting the set S of three vertices indicated, four components remain.Thisshows that the graph is not tough, and we infer from Theorem 18.1 that it isnonhamiltonianAlthough condition (18.1) has a simple form, it is not always easy to apply. Infact, as was shown by Bauer et al. (1990), recognizing tough graphs is Np-hard.。A(a)(b)Fig. 18.2. (a) A nontough graph G, (b) the components of G - SHYPOHAMILTONIAN GRAPHSAs the above example shows, Theorem 18.1 can sometimes be applied to deducethat a graph is nonhamiltonian. Such an approach does not always work. ThePetersen graph is nonhamiltonian (Exercises 2.2.6, 17.1.8), but one cannot deducethis fact from Theorem 18.1. Indeed, the Petersen graph has a very special property: not only is it nonhamiltonian, but the deletion of any one vertex results iniltonian graph (Exercise18.1.16a).Such graphs arecalled hypohamitonianahanDeleting a single vertex from a hypohamiltonian graph results in a subgraph withjustoneconit, and deleting a set S of at least two vertices produces no morethan [s] - 1 components, because each vertex-deleted subgraph is hamiltonian.hence tough.The Petersen graph is an example of a vertex-transitive hvpohamiltonian graph. Such graphs appear to be extremely rare. Another example is theCoreter graph (see Exercises 18.1.14 and 18.1.16c); the attractive drawing of thisgraph shown in Figure 18.3 is due to Randic (1981). Its geetric origins andmany of its interesting properties are described in Coxeter (1983).18.1 Hamiltonian and Nonhamiltonian Graphs 473 If G − S has exactly |S| components, C − S also has exactly |S| components, and the components of C −S are spanning subgraphs of the components of G−S. In other words, C includes a Hamilton path in each component of G − S.
A graph G is called tough if (18.1) holds for every nonempty proper subset S of V . By Theorem 18.1, a graph which is not tough cannot be hamiltonian. As an illustration, consider the graph G of Figure 18.2a. This graph has nine vertices. On deleting the set S of three vertices indicated, four components remain. This shows that the graph is not tough, and we infer from Theorem 18.1 that it is nonhamiltonian. Although condition (18.1) has a simple form, it is not always easy to apply. In fact, as was shown by Bauer et al. (1990), recognizing tough graphs is N P-hard. (a) (b) Fig. 18.2. (a) A nontough graph G, (b) the components of G − S Hypohamiltonian Graphs As the above example shows, Theorem 18.1 can sometimes be applied to deduce that a graph is nonhamiltonian. Such an approach does not always work. The Petersen graph is nonhamiltonian (Exercises 2.2.6, 17.1.8), but one cannot deduce this fact from Theorem 18.1. Indeed, the Petersen graph has a very special prop￾erty: not only is it nonhamiltonian, but the deletion of any one vertex results in a hamiltonian graph (Exercise 18.1.16a). Such graphs are called hypohamiltonian. Deleting a single vertex from a hypohamiltonian graph results in a subgraph with just one component, and deleting a set S of at least two vertices produces no more than |S| − 1 components, because each vertex-deleted subgraph is hamiltonian, hence tough. The Petersen graph is an example of a vertex-transitive hypohamil￾tonian graph. Such graphs appear to be extremely rare. Another example is the Coxeter graph (see Exercises 18.1.14 and 18.1.16c); the attractive drawing of this graph shown in Figure 18.3 is due to Rand´ıc (1981). Its geometric origins and many of its interesting properties are described in Coxeter (1983)