Geometric Structures: Session VIII

Euler's Polyhedral Formula, Steinitz's Theorem, and Eberhard Type Theorems

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

There is little doubt that Euler's Polyhedral Formula is not only one of geometry's most important theorems but also one of the must important theorems in mathematics.

Euler (approximately 1750)

The number of vertices, faces, and edges of a convex 3-dimensional polyhedron obey V + F - E = 2.

In fact, this result holds for polyhedra that are homeomorphic to a sphere, and, thus, include polyhedra that are non-convex but which do not intersect themselves. This also means that faces do not intersect each other. Branko Grünbaum has coined the word acoptic for such polyhedra. Euler's formula can also be thought of a result in graph theory. For a plane connected graph, the number of vertices, faces and edges satisfy V + F - E = 2.

Euler's formula can be generalized to other surfaces. The general result, for graphs embedded on a sphere with n handles, a surface of genus g is that V + F - E = 2 - 2g. (A donut is a sphere with one handle and has genus 1.) Sometimes the term Euler Characteristic is given to the quantity V + F - E. The value of the Euler Characteristic depends on whether a surface is orientable or non-orientable. For the non-orientable case the value of the Euler Characteristic is sometimes given as 2 - k, where k "measures" the non-orientable analogue of handles on a sphere, namely, "crosscaps." Examples, of non-orientable surfaces are the Klein bottle and the Möbius band.

The vertices and edges of a convex polyhedron form a graph. However, it was Ernst Steinitz who found the conditions under which a graph will be the vertex-edge graph of a 3-dimensional convex polyhedron. A graph which is isomorphic to the vertex-edge graph of some 3-dimensional convex polyhedron is called 3-polytopal.

Steinitz (As reformulated in graph theory terminology by Branko Grünbaum and Theodore Motzkin):

A graph is 3-polytopal if and only if the graph is planar and 3-connected.

For example, Figure 1 shows a 3-polytopal graph:

Figure 1

Using Euler's polyhedral formula one can derive the equations below for 3-valent, 4-valent and 5-valent graphs. Here p_k denotes the number of faces of a plane graph which have k sides:

3-valent:

4-valent:

5-valent:

Note that in two of these equations one of the coefficients is zero. This gives rise to the possibility of what has come to be called an Eberhard type theorem. Victor Eberhard was a blind geometer who provided a partial converse to Euler's formula for convex polyhedra. For example, give a solution of (**) above in integers, p_k* (k not 4) one can find a plane 4-valent graph G and a value for the number of 4-sided faces p_k* so that G is 3-connected and p_k(G) for all values of k including 4. Informally, this means that if one has a "free" supply of 4-gons one can make convex 3-dimensional 4-valent polyhedron with specified numbers of faces satisfying (**) if one can use 4-gons as desired.

Here I will outline Grünbaum's original proof which is very lovely and unexpected. Then I will show a slightly simpler (and easier to realize the drawings) proof. 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 p₅ = 1 and p₆ = 1.

Grünbaum's proof constructs a square "block" for each of the k-gons (k ≥ 5). The block is constructed by placing k dots along the left hand side and bottom of a square. The dots are joined in the order 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-3) 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 are "free."

Figure 2

One now takes the individual blocks, one for each k-gon and lays them out along the anti-diagonal of an array. For a block with a 5-gon and 6-gon we get the diagram shown below:

Figure 3

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 to use as many of these as we would like without restriction.

Figure 4

Figure 5

Note that all the interior vertices above are 4-valent, and that there are equal number of vertices along the left and bottom. There are also equal number of vertices along the top and right hand side of the "array." The 4 corners of the square have valence 2 at this juncture and the other vertices have valence three. To finish off his construction Grünbaum joins the vertices b and b', c and c', etc., and x and x' (in this example there is only one pair of such vertices but usually there will be many), etc. Finally, a is joined to a' with two curved lines one going past T and the other past T' and T is joined to T' with two curved lines one going to the left and over the the top and the other going along the bottom and up the right side. The result is a 4-valent graph, and many 4-gons. The 8 extra triangles that Euler's 4-valent relation requires are clustered four at T and four at T'.

With Grünbaum's pioneering proof to inspire, other proofs were developed. The one that follows is due to Ernst Jucovic, a Czechoslovakian mathematician, now deceased.


We start with the graph depicted in the diagram below, where we would have used more "vertical" lines between the four indicated 3-gons had there been more k-gons (k bigger than 4) that we wanted to have in the final graph. The number of such vertical being one less than the number of k-gons to be added.

Figure 6

The diagram above is now modified by introducing (k-4) triangles for each k-gon to be added as indicated in the diagram below for the 5-gon and 6-gon we wish to have. Note that there are fourteen 3-valent vertices in the graph shown. These vertices lie along the infinite face of the current drawing.

Figure 7

Note that the vertices along the infinite face of the graph above are all 3-valent while all the internal vertices of the graph are 4-valent. To complete the construction we will use the graph shown below: This graph also has four 3-gons, and 4-gons with its internal vertices 4-valent while the vertices on the infinite face are equal in number to the graph above (e.g. 14 vertices) and 3-valent.

Figure 8

If we place the graph with the k-gons (k more than 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.

Grünbaum's new look at Eberhard's original theorem and his 4-valent version open a flood gate of interesting work related to this topic. For example, extending the 4-valent Eberhard Theorem Dalyoung Jeong showed that for any face vector satisfying the 4-valent Euler relation (number of 4-gons not restricted) one can select a value for the number of 4-gons and construct a plane embedding of a 4-valent 3-connected graph which realized the given face vector with the selected value of p₄ and the resulting graph would be a projection of a knot! (Another way of thinking of this is that in the plane drawing if one is moving along any edge and when takes the "middle choice" of edge when one gets to a vertex, that the sequence of edges one generates in this manner forms an Eulerian circuit for the graph.)

Euler's formula for 5-valent graphs is necessary but not sufficient for the existence of 5-valent 3-polytopes. There are results in the spirit of Eberhard's Theorem for this case.