Page 4 :
We begin with a necessary condition., Theorem 6.2.4 If G is Hamiltonian, then for every nonempty proper subset S, of V, w(G-S) < |S]., Proof Let C be a Hamilton cycle in G. Then, since C is a spanning subgraph, of G, w(G-S) < w(C-S). If |S = 1, C-S is a path, and therefore w(C-S) =, 1 = |S|. The removal of a vertex from a path P results in one or two components,, according to whether the removed vertex is an end vertex or an internal vertex of, P, respectively. Hence, by induction, the number of components in C-S cannot, exceed |S|. This proves that w(G-S) < w(C-S) < |S|. O, %3D, It follows directly from the definition of a Hamiltonian graph or from Theorem, 6.2.4 that any Hamiltonian graph must be 2-connected. (If G has a cut vertex v,, then taking S = {v}, we see that w(G-S) > |S|). The converse, however, is not, true. For example, the theta graph of Figure 6.8 is 2-connected but not Hamiltonian., Here, P stands for a u-v path of any length > 2 containing neither x nor y., %3D, Exercise 2.1 Show by means of an example that the condition in Theorem 6.2.4, is not sufficient for G to be Hamiltonian., Exercise 2.2 Use Theorem 6.2.4 to show that the Herschel graph (shown in, Figure 5.4) is non-Hamiltonian.

Page 5 :
1lan Graphs, FIGURE 6.8. Theta graph, (a), (b), FIGURE 6.9. Petersen graph. The solid edges form a 1-factor of P, Exercise 2.3 Do Exercise 2.2 by using Theorem 1.4.10 (characterization the-, orem for bipartite graphs)., If a cubic graph G has a Hamilton cycle C, then G\E(C) is a 1-factor of G., Hence, for a cubic graph G to be Hamiltonian, G must have a 1-factor F such that, G\E(F) is a Hamilton cycle of G. Now, the Petersen graph P (shown in Figure, 1.7) has two different types of 1-factors (Figure 6.9), and for any such 1-factor F, of P, P\E(F) consists of two disjoint 5-cycles. Hence P is non-Hamiltonian., Theorem 6.2.5 is a basic result due to Ore [98], which gives a sufficient condition, for a graph to be Hamiltonian., Theorem 6.2.5 (Ore [98]) Let G be a simple graph with n 2 3 vertices. If, for every pair of nonadjacent vertices u, v of G, d(u) + d(v) > n, then G is, Hamiltonian., Proof Suppose that G satisfies the condition of the theorem but G is not, Hamiltonian. Add edges to G (without adding vertices) and get a supergraph G*, of G such that G* is a maximal simple graph that satisfies the condition of the, theorem but G* is non-Hamıltonian. Such a graph G" must exist since G is non-, Hamiltonian while the complete graph on V(G) is Hamiltonian. Hence foronu, pair u and v of nonadjacent vertices of G*, G*+uv must contain a Hamilton cyele