4.10. A planar graph G is outerplanar if G can be drawn in the plane so that all of its vertices lie on the exterior boundary (on the unbounded region).

(i) Show that K4 and K2,3 are not outerplanar.

(ii) Show if G is an outerplanar graph, then G has no subgraph homeomorphic to K4 or K2,3.

4.16 Let G be a polyhedral graph (simple, plane, degrees 3), each of whose faces is bounded by a pentagon or a hexagon.

(i) Show that G must have at least 12 pentagonal faces.

(ii) Prove that if G has all degrees = 3, then G has exactly 12 pentagonal faces.

4.17 Let G be a simple plane graph with f < 12 and all deg 3.

(i) Prove that G has a face bounded by at most 4 edges.

(ii) Give an example to show that the result in (i) is false if G has 12 faces. HINT: Use a Platonic graph.

4.18 Let G be a simple connected cubic plane graph, and let Ck be the number of k-sided faces in G. Prove that

3C3 + 2C4 + C5 - C7 - 2C8 - 3C9 - . . . = 12

1. Use this result to prove result in 4.16(ii).
2. Use this result to prove there is a face bounded by at most 5 edges.

4.19 Let G be a simple graph with at least 11 vertices and let Gc be G's complement.

(i) Prove that G and Gc cannot both be planar.

(ii) Find a graph with 8 vertices for which G and Gc are both planar (Quite Tricky-Google might help).

A Platonic graph is a planar graph in which all vertices have the same degree d1 and all regions have the same number of bounding edges d2, where d1, d2 > 3.

a) If G is a Platonic graph, show that e = (d1/d2)v and r = (d1/d2)v.

b) Using part (a) and Euler's formula, show that

v(2d1 + 2d2 - d1d2) = 4d2.

c) Since v and 4d2 are positive numbers, we conclude that 2d1 + 2d2 -d1d2 > 0. Use this inequality to prove that (d1 - 2)(d2 - 2) < 4.

d) From part c), find the five possible pairs of positive (integer) values for d1 and d2.