10.3 Euler's Formula261Proof Suppose that K3.3 is planar and let G be a planar embedding of K3.3Because K3.3 has no cycle of length less than four, every face of G has degree aleast four. Therefore, by Theorem 10.10, we have4f(G) ≤d(f) = 2e(G) = 18fEFimplying that f(G)≤4. Euler's Formula (10.2) now implies that2=(G) -e(G)+ f(G)≤6- 9+4=1口which is absurd.Exercises+10.3.1 Show that the crossing number satisfies the inequality cr(G) ≥ m-3n +6,provided that n ≥ 3.10.3.2a) Let G be a connected planar graph with girth k, where h ≥ 3. Show thatm≤k(n - 2)/(k - 2).b) Deduce that the Petersen graph is nonplanar.10.3.3 Deduce Euler's Formula (10.2) from Exercise 10.2.12.10.3.4a)Showthatthecomplementofasimpleplanargraphonatleastelevenverticesb) Find a simple planar graph on eight vertices whose complement is planar.10.3.5 A plane graph is face-regular if all of its faces have the same degreea) Characterize the plane graphs which are both regular and face-regularb) Show that exactly five of these graphs are simple and 3-connected. (They arethe platonic graphs.)10.3.6 The thickness e(G) of a graph G is the minimum number of planar graphswhose union is G. (Thus e(G) = 1 if and only if G is planar.)a) Let G be a simple graph. Show that (G) ≥ [m/(3n - 6)]b)Deduce that e(K,)≥[(n +1)/61+1 and show,using Exercise 10.3.4b,thatequalityholdsforalln<8(Beineke and Harary (1965) proved that equality holds for all n + 9, 10; Battleet al. (1962) showed that 0(Ko) = 3.)10.3 Euler’s Formula 261 Proof Suppose that K3,3 is planar and let G be a planar embedding of K3,3. Because K3,3 has no cycle of length less than four, every face of G has degree at least four. Therefore, by Theorem 10.10, we have 4f(G) ≤ f∈F d(f)=2e(G) = 18 implying that f(G) ≤ 4. Euler’s Formula (10.2) now implies that 2 = v(G) − e(G) + f(G) ≤ 6 − 9+4=1 which is absurd.
Exercises 10.3.1 Show that the crossing number satisfies the inequality cr(G) ≥ m−3n+6, provided that n ≥ 3. 10.3.2 a) Let G be a connected planar graph with girth k, where k ≥ 3. Show that m ≤ k(n − 2)/(k − 2). b) Deduce that the Petersen graph is nonplanar. 10.3.3 Deduce Euler’s Formula (10.2) from Exercise 10.2.12. 10.3.4 a) Show that the complement of a simple planar graph on at least eleven vertices is nonplanar. b) Find a simple planar graph on eight vertices whose complement is planar. ————— ————— 10.3.5 A plane graph is face-regular if all of its faces have the same degree. a) Characterize the plane graphs which are both regular and face-regular. b) Show that exactly five of these graphs are simple and 3-connected. (They are the platonic graphs.) 10.3.6 The thickness θ(G) of a graph G is the minimum number of planar graphs whose union is G. (Thus θ(G) = 1 if and only if G is planar.) a) Let G be a simple graph. Show that θ(G) ≥ m/(3n − 6) . b) Deduce that θ(Kn) ≥ (n + 1)/6 + 1 and show, using Exercise 10.3.4b, that equality holds for all n ≤ 8. (Beineke and Harary (1965) proved that equality holds for all n = 9, 10; Battle et al. (1962) showed that θ(K9) = 3.)