Every count a solid can have

Every corner pays for itself proved Euler’s formula: for every convex solid, the number of corners minus the number of edges plus the number of faces is two. That is an equation with three unknowns, and it leaves a question it cannot answer by itself. Given two numbers, say eleven corners and nine faces, is there a solid with exactly those counts? The formula says it would have eighteen edges; it does not say whether the solid exists.

Zero in four dimensions quoted the answer in three dimensions and noted that the corresponding question in four is open. This essay draws the three-dimensional answer and proves it, both halves. It is due to Ernst Steinitz, in 1906, and it is surprisingly clean: a pair $(V, F)$ belongs to some convex solid exactly when

$$V \le 2F - 4 \qquad \text{and} \qquad F \le 2V - 4.$$

Nothing else is needed. Every pair satisfying both inequalities is the corner-and-face count of some solid, and no other pair is.

The region, read as a picture #

The allowed region is a wedge between two lines through the point $(4, 4)$ — the tetrahedron, the smallest solid, with four corners and four faces. The steep line is $F = 2V - 4$: solids on it have as many faces as possible for their corners. The shallow line is $V = 2F - 4$: as many corners as possible for their faces. Everything between is allowed, including every point of the diagonal $V = F$.

The regular solids sit in revealing places. The cube, with 8 corners and 6 faces, is on the shallow line; the octahedron, with 6 and 8, on the steep one. They are each other’s duals — swap corners for faces — and duality reflects the picture in the diagonal. The dodecahedron and icosahedron, with 20 and 12 and with 12 and 20, are a dual pair on the two lines too, beyond the edge of the figure. The tetrahedron, its own dual, sits at the apex where the lines meet.

Each line is a statement about shape, as the next section proves. Solids on the steep line have only triangular faces; solids on the shallow line have only three edges at each corner. The wedge’s two edges are the two extreme kinds of solid, and every solid lies between them.

Why nothing outside the wedge exists #

The inequalities come from counting the same thing in two ways, which is the counting that proved Euler’s formula run once more.

Every face of a solid has at least three sides. Count the pairs (face, edge of that face) by faces: at least $3F$. Count them by edges: each edge borders exactly two faces, so exactly $2E$. So $2E \ge 3F$, with equality exactly when every face is a triangle. By the same argument with corners instead of faces — every corner meets at least three edges, and every edge has two ends — $2E \ge 3V$, with equality exactly when every corner meets three edges.

Now combine with Euler’s formula, $E = V + F - 2$. Substituting into $2E \ge 3F$ gives $2V + 2F - 4 \ge 3F$, that is $F \le 2V - 4$. Substituting into $2E \ge 3V$ gives $V \le 2F - 4$. Those are Steinitz’s inequalities, and the derivation shows where each comes from: the first is the budget of a solid whose faces are all triangles, the second of one whose corners all meet three edges.

The argument never uses convexity except through Euler’s formula and the two facts that faces have three sides and corners three edges, so it applies just as well to any network drawn on a sphere with those properties. That half of the theorem is complete in a paragraph. It says nothing outside the wedge exists. It does not say that everything inside does.

The edges, squeezed between two bounds #

Euler’s formula makes the edges a dependent quantity, $E = V + F - 2$, but they can also be bounded directly, and the bounds are the same inequalities in another form. From $2E \ge 3F$ and $F = E - V + 2$ comes $E \le 3V - 6$; from $2E \ge 3V$ comes $E \ge \tfrac32 V$. So a solid with $V$ corners has between $\tfrac32 V$ and $3V - 6$ edges.

The upper bound is an old friend. It is the bound on the edges of any graph drawn in the plane without crossings, the fact that the five-colour argument used to find a corner with at most five neighbours, and it holds for solids because the corners and edges of a convex solid, projected from a point just outside one face, form exactly such a drawing. The solids that meet it are the triangulations of the sphere — the steep edge of the wedge. The lower bound is the statement that every corner of a solid meets at least three edges, and the solids that meet it are the simple solids on the shallow edge.

Between the two bounds, every number of edges occurs, since every point of the wedge does. For eight corners, a solid can have any number of edges from twelve — the cube and its relatives — to eighteen, the triangulated solids with eight corners, and the five values in between are realised by solids that are partly triangulated and partly not.

Three families on the three special lines #

The other half is a construction, and the natural place to start is the lines themselves.

A pyramid on a polygon with $n$ sides has $n + 1$ corners — the polygon’s and the apex — and $n + 1$ faces — the base and $n$ triangles. So pyramids give every point $(k, k)$ on the diagonal from $k = 4$ upward. A bipyramid, two pyramids glued base to base, has $n + 2$ corners and $2n$ faces, all triangles, and walks up the steep line in steps of $(1, 2)$. A prism has $2n$ corners and $n + 2$ faces, three edges at every corner, and walks along the shallow line in steps of $(2, 1)$.

So the diagonal and both edges of the wedge are filled. The three families also show the duality at work. The dual of an $n$-sided prism — put a corner at the centre of each face and join corners of adjacent faces — is an $n$-sided bipyramid, and the dual of a pyramid is a pyramid. Duality swaps $V$ and $F$, so it exchanges the two edges of the wedge and fixes the diagonal, exactly as the families do. The pentagonal prism at $(10, 7)$ and the pentagonal bipyramid at $(7, 10)$ are reflections of each other in the diagonal of the opening figure. What remains is the interior, and the families suggest how: a move of $(1, 2)$ and a move of $(2, 1)$, applied to the right starting points, would fill everything.

Two moves that fill the wedge #

Both moves are cut and paste on an existing solid.

Cutting a corner. At a corner where exactly three edges meet, slice it off with a plane close to it. The corner is replaced by a small triangle: three new corners instead of one, three new edges, and one new face. The counts change by $(+2, +1)$ in corners and faces. The solid stays convex, and it now has three new corners each meeting three edges — so the move can be repeated.

Capping a triangle. On a triangular face, glue a shallow tetrahedron, its apex just above the face’s centre. The triangle is replaced by three triangles meeting at the new apex: one new corner, three new edges, two new faces net. The counts change by $(+1, +2)$. The solid stays convex if the apex is close enough to the face, and it now has three new triangular faces — so this move can be repeated too.

Now start from the pyramid at $(k, k)$ — it has a triangular face and a three-edged corner, since every corner of its base meets exactly three edges. Apply $t$ corner cuts and $c$ caps, in any order, and the result has $(k + 2t + c, \; k + t + 2c)$ corners and faces. Every point of the wedge has this form for some $k \ge 4$ and $t, c \ge 0$. If $V \ge F$, take $c = 0$ and $t = V - F$; then $k = 2F - V$, which is at least four precisely because $V \le 2F - 4$. If $F > V$, take $t = 0$ and $c = F - V$, and the other inequality does the same job. The opening figure checks it for every point up to sixteen: each allowed pair is reached, and nothing forbidden is.

Why the moves never run out #

The construction depends on one property that is easy to overlook: after each move, the solid still offers a place for either move to act. A corner cut needs a corner where exactly three edges meet, and a cap needs a triangular face.

Both are self-renewing. Cutting a corner creates a new triangular face, the slice, and three new corners, each of which meets exactly three edges — two along the slice’s sides and one running back along an old edge. Capping a triangle creates three new triangles and a new apex, which meets three edges. So whichever move was made last, the solid has both a three-edged corner and a triangle available, and the next move of either kind can be made. The pyramid starts the process with both: its base corners meet three edges each, and its sides are triangles.

This is the kind of detail a proof by construction lives or dies on. A pair of moves that each consumed the feature the other needed would stall after a step or two, and the wedge would be only partly filled. The moves here were chosen so that each leaves behind exactly what both need — which is why Steinitz’s theorem has a two-paragraph proof rather than a case analysis.

What the construction shows about solids #

The proof is short, but it says more than the counts. It says that the only obstructions to existence are the two counting inequalities — that there is no hidden third constraint lurking in convexity, in the geometry of angles, or in the need for faces to be flat. Whatever combinatorial budget the counting allows, some convex solid spends it.

That is not true of finer questions, and it is worth seeing why the counts are so forgiving. The counts forget which faces meet which. Twelve pentagons, whatever the hexagons asked a finer question — which lists of faces by number of sides occur — and found a gap: no solid has twelve pentagons and exactly one hexagon, though the counts allow it. Steinitz’s region is the coarse shadow of that question, and it has no gaps, because the moves can always adjust by the right amounts. The finer the question, the more room for exceptions.

Steinitz is better known for a second theorem, from 1922, which answers the finest question of all: which networks of corners and edges are the skeletons of convex solids? The answer is the networks that can be drawn in the plane without crossings and that stay connected when any two corners are removed. Every flat graph is a pile of circles gave one proof of the hard direction, by packing circles. The counting theorem here is what that theorem looks like when the network is forgotten and only its sizes remain.

The regular solids, counted #

The five regular solids are where this began, and they are now five points of the wedge.

Each of them sits on an edge of the wedge, because each is extreme in one of the two ways — only triangles, or only three edges at a corner. The tetrahedron is both at once, which is why it is the apex. Regular solids are rigid choices, and rigidity puts them at the boundary; the interior of the wedge is where the irregular, generic solids live. A random convex solid — the convex hull of many points scattered on a sphere, say — has only triangular faces, since four random points almost never lie in one plane, so it sits on the steep line; its dual sits on the shallow one. To land in the interior, a solid needs some faces with four or more sides and some corners with four or more edges, which random constructions never produce and deliberate ones must arrange.

The five regular solids are also the only points of the wedge that can be reached by a solid whose faces are all alike and whose corners are all alike. That is why there are only five, seen from the counts: a regular solid with $p$-sided faces and $q$ edges at each corner has $pF = 2E = qV$, and combined with Euler’s formula that leaves exactly five solutions.

What the wedge cannot show #

The figure shows pairs up to sixteen, which is a check and not a proof: the construction proves the theorem for every pair, and the figure confirms the arithmetic of the construction on the pairs it draws. The figure also treats every allowed point alike, and they are not alike in how many routes lead to them. The point $(10, 10)$ is a nonagonal pyramid, and it is also a tetrahedron with two corners cut and two triangles capped, in any of several orders, and a hexagonal pyramid with one cut and one cap, and many other things; the figure records one route per point, and the variety of routes is part of why so many different solids share a count. It shows nothing about how many different solids share a count. The pair $(8, 6)$ is the cube, but it is also every hexahedron whose corners all meet three edges — some of them very far from cubes — and counting combinatorially different solids with a given count is a hard enumeration problem, solved only for small counts by computer.

The pictures of solids are also deliberately simple: a pyramid, a prism, a tetrahedron with one change. The moves as described produce convex solids, but the argument that they do — that a cut close enough to a corner, or a cap low enough over a face, keeps the solid convex — is a statement about sufficiently small changes, and the drawings show one size of change, not the limit. And the figures cannot show convexity being tested. The theorem is about convex solids; for solids that are allowed to be dented, or to have holes, the counts change — a solid with a tunnel through it has $V - E + F = 0$, as the solid where the answer is not two showed — and the wedge moves accordingly.

Still open: the counts in four dimensions #

In three dimensions the question is closed: two inequalities and a construction. In four dimensions, as zero in four dimensions recorded, the corresponding question is open. A four-dimensional solid has corners, edges, faces and three-dimensional cells, four numbers tied by one equation, and the inequalities that cut out the possible quadruples are not known.

The obstacle is partly that the four-dimensional analogue of the two moves does not reach everything, and partly that there are combinatorial arrangements of cells that close up into a perfectly good three-dimensional sphere and are not the boundary of any convex solid — so the counting and the geometry part company in a way they never do in three dimensions. Whether the ratio of edges and faces to corners and cells can be arbitrarily large is Günter Ziegler’s question of “fatness”, and it is open. The three-dimensional theorem is two inequalities and two moves; the four-dimensional one may not have a description of that kind at all, and the evidence so far — families of polytopes found by clever construction, each pushing the known region a little further — looks more like a frontier being mapped than a boundary being closed.