A Platonic graph is a connected planar graph in which all vertices have the same degree

Chapter 53, Problem 53.12

(choose chapter or problem)

A Platonic graph is a connected planar graph in which all vertices have the same degree r (with 3 r 5) and in whose crossing-free embedding all faces have the same degree s (with 3 s 5). Let G be a Platonic graph with v vertices, e edges, and f faces. a. Prove that vr D f s. How is this quantity related to e? b. Prove that if r D s D 3, then v D f D 4. Conclude that K4 is the only Platonic graph with r D s D 3. c. Prove that e D 2 2 r C 2 s 1 : d. In all, there are nine ordered pairs .r; s/ with 3 r; s 5. Use the equation in part (c) to rule out the existence of Platonic graphs with some of these values. e. For the pairs .r; s/ that were not ruled out in part (d), find a Platonic graph with vertex degree r and face degree s