Page 2 :
°, y, , HGURE 6.8. Theta graph, , (b), , , , (a), , RE 6.9, Petersen graph The solid edges form a 1-factor of P, , 2.2 by using Theorem 1.4.10 (characterization the., , 2.3 Do Exercise 2.4, , xercise 2.., 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 acubic graph G to be Hamiltonian, G must have a 1-factor F such tha, 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., 6.2.5 is abasic result due to Ore [98], which gives a sufficient condition, , , , Theorem, for a graph to be Hamiltonian., , Theorem 6.2.5 (Ore [98]) Let G be a simple graph with n > 3 vertices. If, for every pair of nonadjacent vertices u, V of G, dtu) + d(v) 2 1, 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-Hamiltonian. Such a graph G* must exist since G 1s nonHamiltonian while the complete graph on V(G) is Hamiltonian. Hence, for any, pair u and v of nonadjacent vertices of G*, G*+uv must contain a Hamilton cycle, s, , ite

Page 3 :
FIGURE 6.10. Hamilton path for proof of Theorem 6, , 23, , ie would certainly contain the edge e = uv. Thenc, “10, , Tis v, = v of G* (see Figure 6.10) ~€ is a Hamilton, , ( yas ( ), path u E0 e N(w), Vi-1 ¢ N(v); otherwise, vjv, ... aud, , oul 7 s ae r ~IH=3 6B, Now |g be a Hamilton cycle in G*. Hence, for each vertex adjacent to u, thers, there, , Ul, 1, , i, , of, for every pair of nonadj, G'1s, of G. Thus, G is traceable. O, , woul ¢Vv-(v} nonadjacent to v. But then, <a vertex, dg-(v) S (i — 1) — dg-(u)., -.(u) + dg+(v) <n — 1, and therefore dg(u) + dg(v) Ss, = j, v, , contradiction., ¢ s, , corollary 6.2.6 (Dirac [35]) Jf Gis a simple graph with n > 3 and 5 >, shen G IS Hamiltonian. O :, i, , a), corollary 6.2.7 LetGbea simple graph with n > 3 vertices. If d(u)+d(v) >, ,— | for every pair of nonadjacent vertices u and v of G, then G is traceable., proof Choose anew vertex w and let G’ be the graph GV {w}. Then each vertex, G has its degree increased by one, and therefore, in G’, d(u) + d(v) >n +1, acent vertices. Since |V(G")| =n + 1, by Theorem 6.2.5,, Hamiltonian. If C’ is a Hamilton cycle of G’, then C’—w is a Hamilton path

Page 4 :
Theorem 6.2.8 Let G be a simple graph of order n > 3 vertices. Then G bi, Hamiltonian if, and only if G-+-uv is Hamiltonian for every pair of. nonadjacen,, , vertices u and v with d(u) + d(v) =n., , The last result has been instrumental for Bondy and Chvatal’s definition of the, closure of a graph G., , Definition 6.2.9 The closure of a graph G, denoted cl(G) is defined to be, that Supergraph of G obtained from G by recursively Joining pairs of nonadjacent, vertices whose degree sum is at least n until no such pair exists., , Let {e;,..., €p} and is oo5y Sel) be die cers of new edges added to G to get, , be the first edge in {€1,-.., ep} not belonging to Gp, Thenje;,..., €—) arealiie, both G and Go, and uv = €; € E(G2).LetH =G WP tAlo cosy €i-1}. Then Hig, a subgraph of both G and Gp. By the way, cl(G) is defined, Re ee, , , , dy (u) + dy(v) > n,

Page 5 :
Ne, , 6.2 HamiltonianGraphs 113, , , , , , , , , , , , =, 2, 5, FIGURE 6.11. Closure of a graph, and hences, , do,(u) + do,(v) =n., , But this is a contradiction since u and v are nonadjacent vertices of G2, and G2 is, aclosure of G. Thus, € € E(Gy) and, similarly, each f, € E(Gi). O, , An immediate consequence of Theorem 6.2.8 is the following., Theorem 6.2.11 [fcl(G) is Hamiltonian, then G is Hamiltonian., Corollary 6.2.12 If cl(G) is complete, then G is Hamiltonian., , Exercise 2.14 Determine the closure of the following graph.