## Euler's Polyhedral Formula: Part IISo much power from just the simple relationship: Vertices + Faces - Edges = 2 . . .
For what values of k sides. We can illustrate this notation using the plane graph shown in the diagram below, which also illustrates a 3-valent graph. Each of its vertices has exactly three line segments at a vertex. Note that the line segments are straight line segments and that all of the faces are convex regions except for the 6-gon region which represents the "infinite face."Figure 1 In this plane graph above, we have: (*)
Substituting in Euler's polyhedral formula multiplied by 6 we get: which gives: (**) Using equation (*) above and the fact that and again substituting in (**) and simplifying, we obtain: (***) What is remarkable about this equation is that there is no restriction placed on the number of six-sided faces that are present in a plane 3-valent graph. One can derive analogous formulas for 4-valent and 5-valent plane graphs. A general question is: Which sets of non-negative integers that satisfy the "Euler relation" above can arise as the numbers of faces of a 3-valent convex polyhedron? Another question is whether or not a diagram such as the one in Figure 1 can arise from a convex polyhedron. The graph below is 3-valent and has faces which are at least three-sided. Can you convince yourself that it does not correspond to any convex 3-dimensional polyhedron, but that there is a non-convex 3-dimensional polyhedron which does have this as its edge-vertex graph? The polyhedron, when you find it, has four triangular faces and two hexagonal faces! In a rather curious situation, the solution to this problem, finding conditions on a graph that it be isomorphic to (have the same structure as) the vertex-edge graph of a convex 3-dimensional polyhedron, was completely answered in the early part of the 20th century. This work was done by the great German geometer and algebraist Ernst Steinitz (1871-1928). Steinitz's work was published in German and, unfortunately, did not become widely known for quite some time. The catalyst for the reformulation of what Steinitz had done was the "translation" of his work into modern graph theory terminology. This was done by the distinguished geometer Branko Grünbaum. Grünbaum became interested in polyhedra during his graduate studies in Israel and was focused by work he did with Theodore Motzkin (1908-1970) on the combinatorial structure of polyhedra. Amazingly, Steinitz's Theorem enables one to study the combinatorial theory of 3-dimensional convex polyhedra by drawing diagrams in 2 dimensions! Whereas there were almost no mentions of what Steinitz had done between the time when Steinitz published his original theorem and Grünbaum's reformulation, after the reformulation there was a flood of new results. These appeared in areas involving Hamiltonian circuits (a tour of the vertices, starting and ending at the same vertex, visiting each vertex once and only once), coloring problems, and matchings (disjoint sets of edges). Perhaps the greatest progress concerned existence theorems for 3-dimensional convex polyhedra. Such questions now were reduced to constructions of planar graphs. k-gonal faces of G which are interior to the circuit H, and let p'' denote the number of _{k}k-gonal faces of G which are exterior to the circuit H. Figure 2 For the diagram above and the Hamiltonian circuit shown in blue we have four interior faces (labeled in red) which are a 3-, 4-, 6-, and 7-gon. The faces which are exterior to the blue Hamiltonian circuit (labeled in green) are a 3-gon, two 4-gons, a 5-gon, and a 6-gon. Grinberg's Theorem states that the following relationship must hold between the faces lying in the interior and exterior of such a Hamiltonian circuit:
(***) A natural question to ask is: Given a solution of this equation in non-negative integers, does there exist a convex 3-dimensional polyhedron P such that the number of sides of the faces of P are the given ones? For example, it is not difficult to see that p = 1 satisfy (***), but there is no plane 3-valent 3-connected graph with 13 pentagonal faces and 1 heptagonal face. However, because there is no restriction on the value of _{7}p for a plane graph, the following question arises. Given a solution S of (***) in non-negative integers, can one choose a value of _{6}p and construct a plane 3-connected graph that has the chosen value of _{6}p and the values of faces given by S? It was this problem that a blind 19th century geometer, Victor Eberhard, raised and thought he had solved in his book _{6}Zur Morphologie der Polyeder. Although Eberhard's "Theorem" was given by Eberhard, his proof does not meet modern standards of rigor. Branko Grünbaum, using Steinitz's Theorem, was able to give a proper proof of Eberhard's Theorem. However, the proof and some extensions and generalizations of the original proof and theorem are somewhat technical. Branko Grünbaum considered the 4-valent analogue of Eberhard's Theorem whose proof is a tour de force and a mathematical gem. The Euler relation for plane 4-valent graphs is: (****) Here I will outline Grünbaum's original proof, which is very lovely and unexpected. Then I will show a slightly simpler proof (with easier-to-realize drawings). Rather than show a general proof, I will show an example which indicates how to proceed in the general case. First, note that what the 4-valent Euler relation tells us is that every 4-valent 3-polytopal graph (i.e. plane, 4-valent, 3-connected) has 8 triangles, and ( p = 1, and we are allowed to use as many 4-gons as we would like, since they are unrestricted by the 4-valent Euler relation (****)._{6}Grünbaum's proof constructs a square "block" for each of the k-gons (k ≥ 5). The block is constructed by placing k-4 dots along the left hand side and bottom of a square (note: these dots do not include those already at the corners). The dots are joined in the order of top dot on the left to the left dot on the bottom. Next, one joins the next dot down on the left to the next dot to the right on the bottom, etc.. Note that this results in a group of (k-4) triangles hugging a k-sided region in the square. The internal vertices in the block are 4-valent, and the other faces within the block are all 4-gons, which can be used as generously as we want.
Grünbaum now adds additional horizontal and vertical edges to create the situation below. Note that in doing so only 4-gon regions are added, but we are allowed as many of these as we would like.
If we place the graph with the i-valent:Since the coefficient of It is easily seen that since
These rows correspond to the regular tetrahedron, the regular octahedron, the regular icosahedron, the cube, and the regular dodecahedron. Euler's formula has a spawned a seemingly endless stream of mathematical results. May that stream never stop!
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 |