Eberhard's theorem for bipartite polyhedra with one big face
Eberhard’s theorem is a topic in the combinatorial theory of convex polyhedra that once saw a lot of research, but has faded from more recent interest. It’s named after Victor Eberhard, a German mathematician from the late 19th and early 20th century who worked in geometry despite becoming blind at age 12 or 13. I find this hard to imagine, as my own research in geometry is based very heavily on visual thinking, but he was far from the only successful blind mathematician; Leonhard Euler, Lev Pontryagin, and Bernard Morin also come to mind, and there are more.
Anyway, Eberhard’s theorem concerns the following question. Suppose I tell you that a polyhedron has a certain number of faces of certain types. For instance, after Archimedes’ work on polytopes was lost, all we knew about the Archimedean solids until their rediscovery in the Renaissance was a brief listing from Pappus of Alexandria giving this information: there is one with 8 triangles and 6 squares, etc. How can we tell that these counts of faces actually determine a polyhedron?
The given information for Eberhard’s theorem, then, is just a collection of counts of face types (triangles, quadrilaterals, etc.), without specifying the exact shapes of these faces. The goal is to use these faces to build a simple polyhedron, one for which three edges meet at every vertex (like a cube, unlike an octahedron). One necessary condition for this to be possible is that the polyhedron must obey Euler’s polyhedral formula \(v-e+f=2\). And it’s easy to calculate the numbers of vertices, edges, and faces appearing in this formula, from the face counts. Plugging these numbers into Euler’s formula leads to a linear equation that the face counts must obey. Crucially, this linear equation omits the count of hexagons: adding or removing hexagons will not change whether Euler’s formula holds. What Eberhard’s theorem states is that, as long as the face counts obey Euler’s formula in this way, there is always some number of hexagons that can be added or removed so that the remaining faces will form a polyhedron.
However, calculating the fewest number of hexagons needed, or even determining whether a given number of faces of all types (including hexagons) can be put together into a polyhedron, remains somewhat mysterious. So I thought I’d play with a case that would be both simple enough to solve and still interesting: the bipartite simple polyhedra (famous from Barnette’s conjecture), with one big face (a \(2n\)-gon for some \(n>3\)), many small faces (\(n+3\) quadrilaterals, the number needed to make Euler’s formula hold), and a mysterious number of hexagons. What is the smallest number of hexagons that will allow the construction of a simple polyhedron with these face counts? The answer turns out to be \(\lfloor (3n-6)/2\rfloor\), achieved with polyhedra (or polyhedral graphs) in which the outer \(2n\)-gon surrounds a cactus tree of 6-vertex cycles (and possibly one 4-vertex cycle), connected to each other by bridge edges:
The central cactus tree can be rearranged, as long as no two bridge edges have adjacent endpoints. For instance, in the graph with the dodecagon outer face, at the bottom of the figure, it’s possible for the middle six-vertex loop to have three connections to the outside polygon on one side and only one connection on the other side, or to have the four-vertex loop in the middle. But I can prove that all optimal solutions have the same overall central cactus tree structure.
I find it easier to think about the following equivalent rephrasing of the optimization problem: instead of finding a minimum number of hexagons that will allow us to build a polyhedron with those face counts, let’s build a polyhedron with one \(2n\)-gon face and the rest quadrilaterals and hexagons, and concentrate on minimizing the number of vertices in this polyhedron. The number of quadrilaterals will automatically come out right, and the number of hexagons will be minimized if the number of vertices is minimized.
Now suppose that we have any simple polyhedron with one \(2n\)-gon face and the rest quadrilaterals and hexagons. Remove the outer \(2n\)-gon from the graph, leaving a conncted subgraph, and look at the biconnected components of this subgraph. For any one component, its outer face in its induced planar embedding must be a simple cycle, with some vertices having degree two in the component (the endpoints of edges connecting the component to the rest of the graph) and some having degree three. If the component is a 4-cycle or 6-cycle, then all of its vertices have degree two. But if not, then at most four consecutive vertices of its outer cycle can have degree two, because they and the two vertices connected to them on both sides form part of the boundary of a face interior to the component, which can have at most six vertices. And the degree-three vertices of the outer cycle must come in consecutive pairs, which cannot be adjacent to the endpoints of bridge edges connecting to other biconnected components, because a degree-three vertex next to a bridge edge or next to two other degree-three vertices would combine with part of the outer \(2n\)-gon to form a face with seven or more vertices, and a degree-three vertex by itself would form a pentagon, neither of which is allowed.
So in a component that is not a 4-cycle or 6-cycle, the degree-two and degree-three vertices alternate around the outer cycle of the component in consecutive sequences of at most four and exactly two vertices. This implies that the number of degree-two vertices is even (because the whole cycle is even by bipartiteness) and that the number of degree-three vertices in the component (even just counting the ones on its boundary) is at least half of the number of degree-two vertices on its boundary. For the cactus trees that we’ve been using, on the other hand, the number of degree-three vertices in each cactus tree is strictly less than half of the number of degree-two vertices. So if we replace a whole non-cycle component by a cactus tree, we can get a graph with the same number of exposed degree-2 vertices, but fewer total vertices. After repeated replacement of biconnected components, at each step reducing the number of vertices, we would reach a state where the subgraph inside the \(2n\)-gon is a cactus tree. It might not meet the requirement that its bridge edges have nonadjacent endpoints, but it could always be rearranged to do so. And it might not be a cactus with at most one 4-cycle, but if not we could replace two 4-cycles by one 6-cycle and make it even smaller. So the only graphs that cannot be made smaller are the ones we started with, the cactus trees of 6-cycles and at most one 4-cycle, surrounded by an outer \(2n\)-gon.