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. Figure 1 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." Figure 2 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 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 E 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 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 Since the sphere has no 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 |