Mathematics for Computer Science

12.7. Classifying Polyhedra 489

be two neighbors,n 1 andn 2 , ofgthat are not adjacent. Now mergen 1 and

ginto a new vertex,m. In this new graph,n 2 is adjacent tom, and the graph

is planar by Lemma 12.6.2. So we can then mergemandn 2 into a another

new vertex,m^0 , resulting in a new graph,G^0 , which by Lemma 12.6.2 is

also planar. SinceG^0 hasv 1 vertices, it is five-colorable by the induction

hypothesis.

Now define a five coloring ofGas follows: use the five-coloring ofG^0 for

all the vertices besidesg,n 1 andn 2. Next assign the color ofm^0 inG^0 to

be the color of the neighborsn 1 andn 2. Sincen 1 andn 2 are not adjacent

inG, this defines a proper five-coloring ofGexcept for vertexg. But since

these two neighbors ofghave the same color, the neighbors ofghave been

colored using fewer than five colors altogether. So complete the five-coloring

ofGby assigning one of the five colors togthat is not the same as any of

the colors assigned to its neighbors.



12.7 Classifying Polyhedra

The Pythagoreans had two great mathematical secrets, the irrationality of

p

2 and

a geometric construct that we’re about to rediscover!

Apolyhedronis a convex, three-dimensional region bounded by a finite number

of polygonal faces. If the faces are identical regular polygons and an equal number

of polygons meet at each corner, then the polyhedron isregular. Three examples

of regular polyhedra are shown in Figure 12.13: the tetrahedron, the cube, and the

octahedron.

We can determine how many more regular polyhedra there are by thinking about

planarity. Suppose we tookanypolyhedron and placed a sphere inside it. Then we

could project the polyhedron face boundaries onto the sphere, which would give

an image that was a planar graph embedded on the sphere, with the images of the

corners of the polyhedron corresponding to vertices of the graph. We’ve already

observed that embeddings on a sphere are the same as embeddings on the plane, so

Euler’s formula for planar graphs can help guide our search for regular polyhedra.

For example, planar embeddings of the three polyhedra in Figure 12.1 are shown

in Figure 12.14.

Letmbe the number of faces that meet at each corner of a polyhedron, and letn

be the number of edges on each face. In the corresponding planar graph, there are

medges incident to each of thevvertices. By the Handshake Lemma 11.2.1, we