47918.2NonhamiltonianPlanarGraphsFig.18.7.ttegraplthe only known enpleof a nonhamiltonian 3-connected cubic planargraph.Butthen Grinberg (1968) discovered a simple necessary condition for a plane graphto be hamiltonian. His discovery led to the construction of many nonhamiltonianplanar graphs.Theorem18.2GRINBERG'S THEOREMgraph with a Hamilton cycle C. ThenLetGbeaplan-2)( - ) = 0(18.2)where o and o are the numnbers of faces of degreei contained in Int C and ErC, respectively.Proof Denote by E' the subset of E(G))E(C) contained in Int C, and set m' :=|E'J. Then Int C contains exactly m’+1 faces (see Figure 18.8, where m' - 3 andthe four faces all have degree four).Therefore(18.3)0=m+1三Now each edge in E' lies on the booftusin Int C.and each edge ofC lies on the boundary of exactly one face in Int C. ThereforeZi0l=2m + n(18.4)18.2 Nonhamiltonian Planar Graphs 479 Fig. 18.7. The Tutte graph the only known example of a nonhamiltonian 3-connected cubic planar graph. But then Grinberg (1968) discovered a simple necessary condition for a plane graph to be hamiltonian. His discovery led to the construction of many nonhamiltonian planar graphs. Theorem 18.2 Grinberg’s Theorem Let G be a plane graph with a Hamilton cycle C. Then n i=1 (i − 2)(φ i − φ i ) = 0 (18.2) where φ i and φ i are the numbers of faces of degree i contained in Int C and Ext C, respectively. Proof Denote by E the subset of E(G)\E(C) contained in Int C, and set m := |E |. Then Int C contains exactly m + 1 faces (see Figure 18.8, where m = 3 and the four faces all have degree four). Therefore n i=1 φ i = m + 1 (18.3) Now each edge in E lies on the boundary of two faces in Int C, and each edge of C lies on the boundary of exactly one face in Int C. Therefore n i=1 iφ i = 2m + n (18.4)