18.2Nonhamiltonian Planar Graphs481that it only has faces of degrees five, eight, and nine, Grinberg's Identity (18.2)yields3( - ) + 6(s - ) + 7(% - ) = 0We deduce that7(g - ) = 0 (modulo 3)But this is clearly impossible, because the value of the left-hand side is 7 or -7depending on whether the unique face of degree nine lies in Int C or in Ext CTherefore the graph cannot be hamiltonian.The Grinberg graph is an example of a nonhamiltonian 3-connected essentilly4-edge-connected cubic planar graph. Tutte (1956) showed, on the other handthat every 4-connected planar graph is hamiltonian. (Thomassen (1983b) found ashorter proofof this theorem.but his proof is still too complicated to be presentedhere.Thebasicidea is discussed in Section 18.6.)In applying Grinberg's Identity,the parities of theface degrees play acrucial role. This approach fails to provide examples of bipartite nonhamiltonianonnectedcubicplanaraphs.Indeed.Barnette(1969).and independentlyKelR-CCmans and Lomonosov (1975),conjectured that there are nosuch graphs.BARNETTE'SCONJECTUREConjecture 18.3 Every 3-connected cubic planar bipartite graph is hamiltonianPlanbipartite graph was constructed by J. D. Horton (see Bondy and Murty (1976)p.240). The smallest example known of such a graph was found independently byKelmans(1986,1994)andGeorges(1989).Itisshown inFigure18.10Historical note. Interestingly, and ironically, Grinberg's Identity (18.2) wasknown already to Kirkman (1881), some ninety years earlier. But Kirkman, coivinced that every 3-connected cubic planar graph was hamiltonian, used it as atool in searching for Hamilton cycles in particular examples of such graphsIn the next section.we derive various sufficient conditions for hamiltonicityExercises18.2.1a) Show that no Hamilton cycle in the pentagonal prism (the graph Gr in Figre 18.11) can contain both of the edges e and elb) Using (a), show that no Hamiton cycle in the graph G2 can contain both ofthe edges e and e'.18.2 Nonhamiltonian Planar Graphs 481 that it only has faces of degrees five, eight, and nine, Grinberg’s Identity (18.2) yields 3(φ 5 − φ 5 ) + 6(φ 8 − φ 8 ) + 7(φ 9 − φ 9 )=0 We deduce that 7(φ 9 − φ 9 ) ≡ 0 (modulo 3) But this is clearly impossible, because the value of the left-hand side is 7 or −7, depending on whether the unique face of degree nine lies in Int C or in Ext C. Therefore the graph cannot be hamiltonian. The Grinberg graph is an example of a nonhamiltonian 3-connected essentially 4-edge-connected cubic planar graph. Tutte (1956) showed, on the other hand, that every 4-connected planar graph is hamiltonian. (Thomassen (1983b) found a shorter proof of this theorem, but his proof is still too complicated to be presented here. The basic idea is discussed in Section 18.6.) In applying Grinberg’s Identity, the parities of the face degrees play a cru￾cial role. This approach fails to provide examples of bipartite nonhamiltonian 3-connected cubic planar graphs. Indeed, Barnette (1969), and independently Kel￾mans and Lomonosov (1975), conjectured that there are no such graphs. Barnette’s Conjecture Conjecture 18.3 Every 3-connected cubic planar bipartite graph is hamilto￾nian. Planarity is essential here. An example of a nonhamiltonian 3-connected cubic bipartite graph was constructed by J. D. Horton (see Bondy and Murty (1976), p.240). The smallest example known of such a graph was found independently by Kelmans (1986, 1994) and Georges (1989). It is shown in Figure 18.10. Historical note. Interestingly, and ironically, Grinberg’s Identity (18.2) was known already to Kirkman (1881), some ninety years earlier. But Kirkman, con￾vinced that every 3-connected cubic planar graph was hamiltonian, used it as a tool in searching for Hamilton cycles in particular examples of such graphs. In the next section, we derive various sufficient conditions for hamiltonicity. Exercises 18.2.1 a) Show that no Hamilton cycle in the pentagonal prism (the graph G1 in Fig￾ure 18.11) can contain both of the edges e and e . b) Using (a), show that no Hamilton cycle in the graph G2 can contain both of the edges e and e .