A polyhedron is two properties of a graph

A structure with the distances thrown away begins by discarding every coordinate a structure had and keeping only which site is joined to which. The question this essay asks is what can be recovered afterwards, and the answer for one class of objects is: everything.

A convex polyhedron has a graph — its corners, and the edges between them. Steinitz proved in 1922 that the graphs arising this way are exactly the graphs satisfying two conditions, and that neither condition mentions a length, an angle, a coordinate or a notion of convexity.

The two conditions #

A graph is the corner-and-edge graph of a convex polyhedron if and only if it is planar — it can be drawn in the plane with no two edges crossing — and 3-connected — removing any two of its vertices leaves the rest in one piece.

That is the whole statement. It is worth pausing on how little it asks for. A polyhedron is a solid object: it has vertices at particular points of space, faces that are flat, and a boundary that bulges outward rather than inward. None of that survives into the graph, and the theorem says none of it needs to. Hand over a graph passing both tests and a convex polyhedron with that graph exists; hand over one failing either and no polyhedron has it, however cleverly its corners are placed.

Three-connectivity has a second description that says more clearly what it is protecting. Menger’s theorem makes “no two vertices separate the graph” equivalent to “between any two vertices there are three paths sharing no vertex but their ends”. Read that way the condition is about redundancy rather than about removal: every pair of corners of a polyhedron is joined three independent ways round its surface, and it is joined three ways because the corner sits inside a two-dimensional boundary with no pinch in it. The removal test used here is the cheaper form of the same statement, and it is the form a computer can run without constructing anything.

Planarity is the condition with the geometric content, and its relation to a polyhedron is direct rather than analogical. Put a light source just outside the middle of one face of a convex polyhedron and let it cast the edges onto a plane beyond. The face nearest the light opens out to become the boundary of the picture, every other face lands inside it, and no two edges cross, because the polyhedron is convex and nothing occludes anything. What comes out is a plane drawing of the graph, and the outer region of that drawing is a face like any other. Convexity is what makes the projection work; it is spent in producing the drawing, and afterwards it is not needed.

Three-connectivity is the condition that looks like bookkeeping and is not. Its job is to keep the graph from having a place where it can be pulled apart, and the reason a polyhedron cannot have one is easiest to see by trying to build the counterexample. Suppose a graph falls into two pieces when a single vertex is removed. In a polyhedron that vertex would be a corner at which two otherwise separate solids meet at a point, and the result is not convex — the neighbourhood of that corner has a pinch in it, and a convex body has no pinches. Suppose instead that two vertices separate it. Then the polyhedron would have to be squeezed to a segment somewhere, which is the same objection one dimension up.

The five accepted graphs were chosen so that no two of them pass for the same reason. Three are the graphs of solids with all faces alike; the triangular prism has two kinds of face and the pyramid on a square has two kinds of vertex, so between them the plate contains a graph that is neither vertex- nor face-transitive. The pyramid is the useful one to keep in mind, because its apex has degree four and its base corners degree three, and nothing in either condition mentions degree at all. A graph can pass with vertices of any degrees from three upward — three is forced, since a corner of a convex polyhedron meets at least three edges — and the theorem never asks whether they agree.

There is a second thing three-connectivity buys, and it is the one that makes the theorem worth stating as a fact about graphs rather than about drawings. Whitney proved that a 3-connected planar graph has essentially only one plane drawing: the set of faces is the same however the drawing is made. So “the faces of a polyhedron” is a property of the graph, not of the projection or of the polyhedron’s shape. Without 3-connectivity that fails, and a planar graph can have genuinely different face sets in different drawings — which would leave the phrase “the faces” undefined and the whole combinatorial account of polyhedra without an object to be about.

Duality is the clearest payoff of the faces belonging to the graph. Every convex polyhedron has a dual, got by putting a vertex inside each face and joining two of them when their faces share an edge, and the dual of the dual is the original. That construction reads faces as inputs, so it needs the faces to be determined — and 3-connectivity is what determines them. The plane dual of a 3-connected planar graph is again planar and 3-connected, so the class of graphs this theorem describes is closed under an operation that is otherwise defined only on solids. Every parallelohedron is a shadow of a cube uses that closure without remarking on it, since the projections it takes are described face-by-face and the faces have to exist first.

Why neither condition can be dropped #

A theorem with two hypotheses invites the question of whether one of them is doing the work. It is answered by exhibiting a graph that fails each condition while passing the other, and the four smallest such graphs are the four in the table that are not polyhedra.

The complete graph on five vertices is 3-connected — removing two of its five vertices leaves three that are all joined to each other — and it is not planar. The complete bipartite graph joining three vertices to three others is 3-connected for the same reason and is also not planar. Those two are not an arbitrary choice of counterexample: Kuratowski’s theorem says they are the only obstructions there are, in the sense that a graph is non-planar exactly when one of them can be found inside it after contracting edges. So the first condition has precisely two ways to fail, and both are on the plate.

Going the other way, two tetrahedra glued at a single shared vertex are perfectly planar — the picture shows the drawing — and one vertex removal splits them. A square is planar and falls apart when two opposite corners are removed. Neither is a polyhedron, and neither is exotic; the second is a shape a reader has drawn thousands of times, and the reason it is not a polyhedron is that it is not a solid at all.

At the other end, the smallest graph passing both conditions is the complete graph on four vertices, and it passes them for reasons that leave no room to spare. Removing any two of its four vertices leaves two vertices joined by an edge, so it is 3-connected and could not be on fewer vertices, since three vertices cannot survive two removals. Its six edges meet the planar bound of 3 × 4 − 6 exactly, so it is planar and no edge could be added. The tetrahedron is therefore the polyhedron with the fewest corners in the same sense in which every net with one vertex, counted finds the smallest periodic graphs — by an enumeration that runs out rather than by an appeal to what a polyhedron ought to look like.

The square is worth a moment, because it is the case where the graph is doing something a drawing cannot show. Four vertices in a cycle is the graph of a square, of a rectangle, of a rhombus and of an arbitrarily wild quadrilateral, and it is the graph of no polyhedron whatever. The theorem says so on connectivity grounds and gives no other reason, which is the right answer: a flat quadrilateral is not a degenerate polyhedron in need of a special case, it is simply outside the class.

Where the bound comes from #

Non-planarity is decided here by arithmetic rather than by an algorithm, and the arithmetic is Euler’s.

A connected plane drawing satisfies V − E + F = 2. Every face is bounded by at least three edges and every edge borders exactly two faces, so counting edge-face incidences two ways gives 3F ≤ 2E. Substituting into Euler’s formula gives E ≤ 3V − 6. A graph with no triangles needs at least four edges around every face, 4F ≤ 2E, and the bound tightens to E ≤ 2V − 4.

That is enough to settle both non-planar cases exactly. The complete graph on five vertices has ten edges against a bound of nine, so it is not planar. The complete bipartite graph on three and three has nine edges against a general bound of twelve, which it comfortably meets — and it has no odd cycles, so the applicable bound is eight, and nine exceeds it. Had bipartiteness not been tested, that graph would have passed and the census would have called it a polyhedron.

The asymmetry between the two directions is worth stating plainly. Exceeding the bound proves non-planarity outright. Meeting it proves nothing at all — there are graphs well under the bound that are still non-planar, obtained by taking one of the two obstructions and hanging a long path off it. So the arithmetic here is a proof of failure and never a proof of success, and planarity for the five accepted graphs is established by exhibiting the crossing-free drawings rather than by any count.

Why the alternating sum is two rather than some other number is worth one sentence, since it is the only place a surface enters. A plane drawing of a connected graph is a drawing on a sphere, with the outer region of the plane closing up into the face containing the point at infinity, and two is the Euler characteristic of the sphere. Draw the same graph on a torus instead and the sum is zero, the incidence argument gives E ≤ 3V with no subtraction, and every bound above loosens accordingly.

One consequence of the formula deserves separating out, because it is what five solids from one inequality runs on. Once a graph is known to be planar, the number of faces is not free: it is 2 − V + E, determined by the two counts already in hand. Combined with the incidence inequalities, that turns questions about which polyhedra can exist into questions about which integer solutions a small system has — and the classification of the regular solids is exactly such a question, solved by an inequality with five solutions and no sixth.

What this says about a net #

A crystal net is a graph, so every question here can be asked of one, and two of the answers are useful.

The first is a warning about what a net records. A net is a choice of what counts as a bond shows that the graph obtained from a structure depends on where the cutoff was put, and the theorem here shows how much that choice decides. A cutoff that admits one bond too few can leave a coordination polyhedron’s graph 2-connected instead of 3-connected, and the object it then describes is not a polyhedron at all. That is not a rounding error in a description; it is a different kind of object, and no amount of care with the coordinates afterwards recovers what the cutoff threw away.

The second is about the coordination polyhedra a structure is usually described by. Naming the shape around a cation — a tetrahedron, an octahedron, a cube — is naming a graph, and the theorem says which of those names are available. The graph must be planar and 3-connected, and if a proposed coordination figure’s graph is not, the figure is not a convex polyhedron and the description is using the word loosely. That test costs nothing to run and it is the graph that answers it, which is convenient because a structure determination hands over connectivity long before it hands over a reliable shape.

There is a third reading, about the polyhedral units a framework structure is described in terms of. A zeolite’s cage, a Keggin ion’s shell, a fullerene — these are named as polyhedra and the naming is a claim about a graph. Where the claim is checkable it is checkable by the two conditions, and where it fails the honest description is a graph on a surface that is not a sphere. Counting outwards counts the neighbours at each distance in a net and finds the counts follow a quasi-polynomial; the same count run on a finite cage terminates instead, and the length at which it terminates is a property of the cage’s graph. So the finite and infinite descriptions of a structure are the same kind of object measured to different depths, and only the finite pieces are candidates for being polyhedra.

Where the theorem stops being applicable is equally worth naming. A periodic net is infinite, so neither condition applies to it directly — every net folds onto a torus shows what the finite object standing in for it is, and that object is a graph on a torus rather than on a sphere. Planarity is exactly the statement that a graph draws on a sphere, and the whole content of the quotient description is that a net’s finite form draws on something else. So Steinitz’s theorem is about the finite pieces of a structure — its coordination figures, its cages, its polyhedral building units — and not about the structure as a whole.

The fifth of those is the one that shows the arithmetic is doing real work. The octahedron’s graph meets the edge bound with equality — twelve edges on six vertices, and 3 × 6 − 6 is twelve — and equality in that bound holds exactly when every face is a triangle, since the inequality it came from was 3F ≤ 2E. So the count alone establishes that every face of the octahedron is a triangle, without any of its faces being examined. That is the shape of a good combinatorial argument: a number computed from two other numbers, forcing a fact about the object that was not put in.

Where this stops #

The hard half of Steinitz’s theorem is the half not demonstrated here. Showing that a polyhedron’s graph is planar and 3-connected is the projection argument above, and it is short. Showing that every planar 3-connected graph is realised by some convex polyhedron is a construction, and every known proof of it is substantial — the original works by reducing any such graph to the tetrahedron through a sequence of edge contractions and building the polyhedron back up along that sequence. What is computed here is the test rather than the construction.

There is also a quantitative question the theorem is silent on. It says a realising polyhedron exists; it says nothing about how large its coordinates must be, and for a graph on n vertices the best known constructions can need coordinates exponential in n. Whether polynomial-size coordinates always suffice is open. So a graph passing both tests is certainly a polyhedron, and finding the polyhedron may still be hard — which is the same gap between existence and construction that the polyhedra that can flex meets from the other side, where a count promises a motion and does not produce one.

One dimension up the analogue simply fails, and knowing that is what stops the theorem from being read as an instance of a pattern. There is no known characterisation of the graphs of four-dimensional convex polytopes, and none is expected: deciding whether a given complex is a polytope is hard in a precise sense, and the combinatorial types of 4-polytopes have resisted the kind of clean two-condition statement that settles three dimensions completely. Steinitz’s theorem is a low-dimensional accident, and a fortunate one. That is the same shape of result as the count that promises a mechanism, where a counting argument that decides a question outright in one setting only ever gives a necessary condition in another.

Finally, the class of graphs tested here is small and deliberately so. Nine graphs cannot be evidence about graphs in general; they are the smallest witnesses to the statements the essay makes, which is a different job. The conditions themselves are decidable for any graph — 3-connectivity by the removals shown, and planarity by algorithms that run in time proportional to the number of vertices — so the smallness is a choice about what can be drawn on a page rather than a limit on what can be tested.