290 6 Combinatorics and Probability
connected. The number of edges has decreased by 1; that of faces has also decreased by
- By the induction hypothesis,
V−(E− 1 )+(F− 1 )= 2 ;hence Euler’s formula holds for the original graph, too. This completes the proof.
This method of proof is called reduction of complexity, and is widely applied in a
combinatorial branch of geometry called low-dimensional topology.
As a corollary, ifV,E, andF are the numbers of vertices, edges, and faces of a
convex polyhedron, thenV−E+F=2. As you can see, it was much easier to prove
this formula for general planar graphs. The number 2 in Euler’s formula is called the
Euler (or Euler–Poincaré) characteristic of the sphere, since any convex polyhedron has
the shape of a sphere. If a polyhedron has the shape of a sphere withghandles (a so-called
surface of genusg), this number should be replaced by 2− 2 g. The faces of such a graph
should be planar polygons (no holes or handles). The Euler characteristic is an example
of a “topological invariant’’; it detects the number of handles of a polyhedral surface.
As an application of Euler’s formula, let us determine the Platonic solids. Recall that
a Platonic solid (i.e., a regular polyhedron) is a polyhedron whose faces are congruent
regular polygons and such that each vertex belongs to the same number of edges.
Example.Find all Platonic solids.
Solution.Letmbe the number of edges that meet at a vertex and letnbe the number
of edges of a face. With the usual notation, when counting vertices by edges, we obtain
2 E =mV. When counting faces by edges, we obtain 2E =nF. Euler’s formula
becomes
2
mE−E+
2
nE= 2 ,
or
E=
(
1
m+
1
n−
1
2
)− 1
.
The right-hand side must be a positive integer. In particular,m^1 +^1 n >^12. The only
possibilities are the following:
1.m= 3 ,n=3, in which caseE=6,V=4,F=4; this is the regular tetrahedron.2.m= 3 ,n=4, in which caseE=12,V=8,F=6; this is the cube.3.m= 3 ,n=5, in which caseE =30,V =20,F =12; this is the regular
dodecahedron.