Euler's Polyhedral Formula: Part IISo much power from just the simple relationship: Vertices + Faces - Edges = 2 . . .
For what values of k is it possible for a convex polyhedron to have a k-regular graph? It turns out that it is easy to verify from Euler's formula that k can only be 3, 4, or 5. (For arbitrary plane graphs one can also have the case that k = 1 or k = 2.)
In this plane graph above, we have: p3 = 2, p4 = 3, p5 = 1, p6 = 2, and p7 = 1.
Substituting in Euler's polyhedral formula multiplied by 6 we get:
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.
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:
4. Eberhard Type Theorems
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 p5 = 13 and p7 = 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 p6 for a plane graph, the following question arises. Given a solution S of (***) in non-negative integers, can one choose a value of p6 and construct a plane 3-connected graph that has the chosen value of p6 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 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.
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 (k-4) additional triangles for each k-gon. Now, suppose we would like to find a 3-polytopal graph with p5 = 1 and p6 = 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 (****).
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 k-gons (k > 4) on the northern hemisphere of a sphere, with the fourteen 3-valent vertices along the equator, and the diagram with only 4-gons and four triangles on the southern hemisphere of the same sphere matching up its fourteen vertices along the equator, the result is a graph with all 4-valent vertices, and exactly the right number of triangles and k-gons that we wish. Since all the other faces are 4-gons, and these are not restricted by the 4-valent version of Euler's equation, we have constructed a 4-valent plane 3-connected graph which has the properties that were asserted for the 4-valent Eberhard Theorem. One can also look at the values of p4 which can occur as the number of 4-gons for a plane 3-connected graph and which "realizes" the given solution of the 4-valent Euler relation.
Since the coefficient of t2 vanishes in this equation, it is possible to formulate a variety of Eberhard type theorems for various classes of graphs which involve the spanning trees of these graphs.
Simplifying, we obtain:
It is easily seen that since p and q must be at least 3, there are only 5 solutions of this equation in integers:
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