Euler's Polyhedral Formula
Posted December 2004.
A theorem which would make both my list of 10 favorite theorems and my list of 10 most influential theorems . . .
Does it make sense to construct lists related to mathematics? What about a list of the 10 greatest mathematicians? 10 greatest women mathematicians? The 10 most influential theorems? The 10 niftiest theorems?
On the one hand constructing lists is perhaps silly. How can one make a list of the 10 greatest composers of classical music? Must I leave Tchaikovsky out to include Mahler or Handel? Yet, from another perspective constructing lists of this kind makes one think about a wide variety of value-laden issues. What makes a composer great? Should a composer of a few great pieces be put on a short list of greats while another composer who perhaps composed nothing that rose to the heights of the first person, yet composed 100 times as many pieces at a very high level of inspiration, is omitted? This being the first of my last two columns as solo editor of the Feature Column, perhaps readers will indulge me if I write two columns about a theorem which would make both my list of 10 favorite theorems and my list of 10 most influential theorems. This theorem involves Euler's polyhedral formula (sometimes called Euler's formula).
Today we would state this result as: The number of vertices V, faces F, and edges E in a convex 3-dimensional polyhedron, satisfy V + F - E = 2. Aspects of this theorem illustrate many of the themes that I have tried to touch on in my columns.
a. A cube with a triangular tunnel bored through it.
b. The portion of the surface of three pairwise intersecting vertical planes (e.g. "triangular cylinder").
c. The surface formed based on three rays which meet at a point as shown below.
(Problem: The "faces" are not polygons but unbounded portions of planes.)
Almost certainly, in the early days of the study of polyhedra, the word referred to convex polyhedra. A set is convex if the line segment joining any two points in the set is also in the set. Among the nice properties of convex sets is the fact that the set of points in common to a collection of convex sets is convex. Loosely speaking, non-convex sets in two dimensions have either notches or holes. The diagram below shows a non-convex polygon and a convex polygon.
The planar set below is not convex, but note that it does not satisfy the usual definition of a polygon, even through it is bounded by sections of straight lines.
The faces of a convex polyhedron consist of convex polygons. However, this approach to defining polyhedra rules out a "polyhedron" which goes off to infinity, such as the surface below:
This polyhedron has three rays (which, if extended, should meet at a point) and three line segments as edges of the polyhedron, rather than having edges which are line segments. One can also have examples where there are only rays (see earlier diagram).
one can assemble 12 of them, three at each vertex, to form the solid known as the regular dodecahedron.
However, the Greeks knew about the polygon that today is called the pentagram:
This polygon has a good claim to be called a regular polygon because all its sides have equal length and the angle between two consecutive sides of the polygon is always the same. However, this polygon, when drawn in the plane, does not define a convex set and the sides of the polygon intersect each other. Nonetheless, when mathematicians considered the idea of "non-convex" regular polyhedra where such "star polygons" were permitted, they discovered some new examples of "regular polyhedra," now known as the Kepler-Poinsot polyhedra . Later H.S.M. Coxeter and Branko Grünbaum broadened the rules for polyhedra and discovered other "regular polyhedra."
V + F - E = 2.
3. Euler's contribution
Euler mentioned his result in a letter to Christian Goldbach (of Goldbach's Conjecture fame) in 1750. He later published two papers in which he described what he had done in more detail and attempted to give a proof of his new discovery.
Because he did not look at the polyhedra he was studying as graphs, Euler attempted to give a proof of the formula based on decomposing a polyhedron into simpler pieces. This attempt does not meet modern standards for a proof. His argument was not correct. However, results proven later make it possible to use Euler's technique to prove the polyhedral formula.
In the diagram below we have highlighted in turquoise the face of the polyhedron that we remove from this box, and now pretend that the remaining structure is made of rubber.
We now stretch and flatten out the remaining surface so that the turquoise face becomes the unbounded region of the resulting graph that can be drawn in the plane (see Figure 2 below). The position of the red edges is shown to help you visualize what is happening. Of course the turquoise region should be shown as going off to "infinity," even though it appears only as a bounded face in the original polyhedron. The back face of the box is now shown as having a vertical and horizontal red edge. The plane that contains this back face can be thought of as the plane into which we stretch and flatten out the surface of the box with the turquoise face removed. It's fairly clear that the faces of the original polyhedron are preserved by this process. It is also clear where these faces appear in the plane graph representation of the polyhedron, except perhaps for the turquoise face in Figure 1. It is common for people to forget to count this face when they are counting the faces of a graph drawn in the plane. Plane graphs always have at least one face, the "infinite face."
Although there are other ways of seeing that the graphs of convex 3-dimensional polyhedra or graphs on the sphere have planar graphs (i.e. at some stage use stereographic projection), this argument hopefully makes clear that the graphs that can be drawn on a sphere (polyhedra whose graphs are homeomorphic to a sphere) where edges meet only at vertices are the same as the graphs that can be drawn in a plane where edges cross only at vertices.
The blue in this diagram does not go off to infinity but you should think of it as doing that. In the diagram below an edge of one circuit in the graph which bounds a face is shown in red, and this edge is adjacent to the ocean. When the dike represented by this red edge is "breached," the field on the other side of the dike is opened up to the ocean and becomes flooded, as indicated by the turquoise (for illustrative purposes - the color of the water really should be the same as the ocean!).
If a connected graph has circuits that bound faces, one can eliminate one edge from each of these circuits in a way that preserves the property that the graph remains connected. There is a one-to-one correspondence between the edges removed to get to a connected graph without circuits (because of the Jordan curve theorem) and the faces of the graph which are not the infinite face. The edges necessary to do this are shown in red below, and the fact that the fields flood is shown in turquoise.
The resulting graph of black edges forms a spanning tree of the original graph. A spanning tree of a connected graph is a subgraph which is a tree (e.g. a graph which is connected and has no circuit) and includes all the vertices of the original graph. Thus, a spanning tree of a connected graph has the same number of vertices as the original graph, but fewer edges (unless the original graph is a tree). Note that for any tree, we have:
Now, let us count the edges of the original graph by adding the number of edges removed to get a tree, the red edges above, to the number of black edges above. Thus,
Now, we know that ERED is equal to one less than the number of faces of the original graph. This is true because we needed one red edge to flood each dry field (e.g. the non-infinite faces), and the graph had one more face, the infinite face. The number of EBLACK edges is given by one less than the number of vertices in the graph, because the black edges are a spanning tree of the original graph. Hence we have:
Rearranging the terms in this equation gives:
Euler's formula does not hold for any graph embedded on a surface. It holds for graphs embedded so that edges meet only at vertices on a sphere (or in the plane), but not for graphs embedded on the torus, a one-holed donut. The fundamental theorem that is used directly or indirectly in a proof of the Euler polyhedra formula for graphs depends on the Jordan Curve theorem , which states that any simple closed curve divides the plane into three sets, those points on the curve, those inside the curve, and those outside the curve.
If two edges in a graph drawn on a surface cross, one can eliminate the crossing by having one of the edges go over a small handle to avoid the crossing. It turns out that if a graph can be embedded without edges meeting anywhere other than at vertices on a surface with g handles, but on no surface with a smaller number of handles, then:
Since the sphere has no handles, g = 0 for the sphere, and the formula above reduces to Euler's formula. The connection between Euler's polyhedral formula and the mathematics that led to a theory of surfaces, both the orientable and unorientable surfaces, is still being pursued to this day. In addition, motivated by many problems involving the design of computer chips (integrated circuits), there has been an explosion of research about crossing number problems for graphs in the plane. This involves finding the minimum number of crossings when an abstractly defined graph is drawn in the plane. It turns out that the crossing number depends on whether or not the edges are allowed to be straight or curved. Many of these questions involve the use of Euler's formula to get estimates for the smallest number of crossings. Furthermore, Euler's formula is intimately connected with coloring problems of the faces of a graph. These coloring problems include not only the famous 4-color conjecture but also problems about coloring the faces of graphs on surfaces such as spheres with many handles.
Grünbaum, Branko . Polytopes, graphs, and complexes. Bull. Amer. Math. Soc. 76 1970 1131--1201. MR0266050 (42 #959)
Grünbaum, Branko . Regular polyhedra---old and new. Aequationes Math. 16 (1977), no. 1-2, 1--20. MR0467497 (57 #7353)
Grünbaum, Branko . A convex polyhedron which is not equifacettable. Geombinatorics 10 (2001), no. 4, 165--171. MR1825338
Jendrol', Stanislav . A new proof of Eberhard's theorem. Acta Fac. Rerum Natur. Univ. Comenian. Math. 31 (1975), 1--9. MR0385718 (52 #6577)
McMullen, Peter ; Schulte, Egon . Abstract regular polytopes. Encyclopedia of Mathematics and its Applications, 92. Cambridge University Press, Cambridge, 2002. xiv+551 pp. ISBN: 0-521-81496-0 MR1965665 (2004a:52020)
Mohar, Bojan ; Thomassen, Carsten . Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001. xii+291 pp. ISBN: 0-8018-6689-8 MR1844449 (2002e:05050)
Thomassen, Carsten . Planarity and duality of finite and infinite graphs. J. Combin. Theory Ser. B 29 (1980), no. 2, 244--271. MR0586436 (81j:05056) .
Wilson, Robert A. Graphs, colourings and the four-colour theorem. Oxford University Press, Oxford, 2002. viii+141 pp. ISBN: 0-19-851061-6 MR1888337 (2003c:05095)
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance