Mathematics for Computer Science

12.8. Classifying Polyhedra 379

n m v e f polyhedron

3 3 4 6 4 tetrahedron

4 3 8 12 6 cube

3 4 6 12 8 octahedron

3 5 12 30 20 icosahedron

5 3 20 30 12 dodecahedron

Figure 12.16 The only possible regular polyhedra.

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
know:
mvD2e:

Also, each face is bounded bynedges. Since each edge is on the boundary of two
faces, we have:
nf D2e

Solving forvandf in these equations and then substituting into Euler’s formula
gives:
2e
m
eC

2e

n

D 2

which simplifies to
1
m

C

1

n

D

1

e

C

1

2

(12.6)

Equation 12.6 places strong restrictions on the structure of a polyhedron. Every
nondegenerate polygon has at least 3 sides, son 3. And at least 3 polygons
must meet to form a corner, som 3. On the other hand, if eithernormwere
6 or more, then the left side of the equation could be at most1=3C1=6D1=2,
which is less than the right side. Checking the finitely-many cases that remain turns
up only five solutions, as shown in Figure 12.16. For each valid combination ofn
andm, we can compute the associated number of verticesv, edgese, and facesf.
And polyhedra with these properties do actually exist. The largest polyhedron, the
dodecahedron, was the other great mathematical secret of the Pythagorean sect.
The 5 polyhedra in Figure 12.16 are the only possible regular polyhedra. So if
you want to put more than 20 geocentric satellites in orbit so that theyuniformly
blanket the globe—tough luck!