The fewest corners a surface needs

Every surface is sewn from pants cut a surface into the fewest pieces of one kind and found the number fixed by the Euler characteristic. This essay asks for the fewest pieces of another kind, and the answer is different in character. The pieces are triangles, the thing to minimise is the number of corners, and the characteristic gives only a floor. Most surfaces meet the floor exactly. Three do not, and finding out which three took until 1980.

The figure below is the torus built from seven corners, which is the fewest a torus allows. It is drawn unrolled onto a lattice of triangles, with each lattice point labelled by a number from $0$ to $6$; points with the same label are the same corner of the torus, and the fourteen shaded triangles are one complete copy of the surface. The blue corner $0$ sits in six triangles, and its six neighbours carry the labels $1$ to $6$ — every other corner. The same is true of every label. Every pair of the seven corners is joined by an edge, and that is what the fewest corners forces.

What counts as a triangulation #

A triangulation here is stricter than a gluing. The earlier essays built surfaces by pairing the edges of one polygon, and a gluing of that kind can collapse all of a polygon’s corners into a single point: a random gluing usually leaves only a handful of vertices. Triangles glued that freely can make a torus from two triangles and a single corner.

The condition that makes the question interesting is that any two triangles meet in a whole edge, a single corner, or not at all, and no triangle has two corners at the same point. So a triangle is determined by its three corners, an edge by its two, and two corners are joined by at most one edge. It is the condition under which a surface could be built out of flat triangles in space without anything degenerate happening, and it is the one that makes corners expensive.

The floor, in two lines #

Let the triangulation have $n$ corners, $e$ edges and $f$ triangles. Every triangle has three edges and every edge borders exactly two triangles, so $3f = 2e$. The characteristic is $n - e + f = \chi$, the count that does not depend on how a surface is cut up. Together these give

$$e = 3(n - \chi), \qquad f = 2(n - \chi).$$

Now the condition bites. Two corners share at most one edge, so there are at most $n(n-1)/2$ edges. Substituting,

$$\frac{n(n-1)}{2} \ge 3(n - \chi), \qquad\text{that is,}\qquad n^2 - 7n + 6\chi \ge 0.$$

This is Heawood’s inequality, and it says $n$ is at least $\tfrac12\left(7 + \sqrt{49 - 24\chi}\right)$. For the sphere, $\chi = 2$, the floor is four: the tetrahedron. For the projective plane, $\chi = 1$, it is six. For the torus and the Klein bottle, both with $\chi = 0$, it is seven. And a surface that meets the floor exactly has every pair of corners joined by an edge: its edges form the complete graph.

The floor grows like the square root of the characteristic’s size: roughly $\sqrt{12g}$ corners for a surface with $g$ handles. A surface with a hundred handles can be built from thirty-nine corners, which then carry 711 edges and 474 triangles between them. The surfaces with many handles are the ones that are cheap in corners and expensive in everything else.

Seven corners, twenty-one edges, fourteen triangles #

The seven-corner torus was known to August Möbius in 1861, and its triangles have a formula: for each $i$ from $0$ to $6$, the triangles $\{i, i+1, i+3\}$ and $\{i, i+2, i+3\}$, with the arithmetic done modulo $7$. The first figure checks that every lattice triangle is one of these fourteen, that every one of the twenty-one edges borders exactly two of them, that the six triangles round each corner close up into a single disc, and that the whole thing is two-sided with characteristic zero — which, by the classification, is to say it is a torus.

The labelling is the whole construction. The corner at column $a$ and row $b$ of the triangular lattice gets the label $a + 3b$ modulo $7$. Moving one step along the lattice in any of its six directions adds $1$, $3$ or $2$, or subtracts them — six different amounts, so six different neighbours, and since there are only six other labels, every one of them. The lattice rolled up so that equal labels coincide is the torus, and the rolling-up is along the two directions in which the label does not change, which is why the shaded strip of fourteen triangles repeats.

In 1949 Ákos Császár found a way to build this surface in ordinary space out of fourteen flat triangles with no two crossing: the Császár polyhedron, a polyhedron with a hole through it and no diagonals, since every pair of its seven corners is already an edge. It is one of only two polyhedra known with that property, the other being the tetrahedron.

Turn the triangulation inside out — a region round each corner, a border wherever two corners share an edge — and the result is a map of seven countries on the torus, each touching all six others. No colouring of that map uses fewer than seven colours. Lajos Szilassi built it as a polyhedron too, in 1977: seven hexagonal faces, every face sharing an edge with every other.

The colours and the corners are one problem #

That map is the reason the torus needs seven colours where the plane needs four, and the connection runs deeper than one example. Percy Heawood proved in 1890 that a map on a surface of characteristic $\chi \le 0$ never needs more than $\left\lfloor \tfrac12(7 + \sqrt{49 - 24\chi}) \right\rfloor$ colours — the same expression as the corner floor, rounded down instead of up. His argument is the counting above run on the map instead of the triangulation.

It goes like this. Suppose a map needs $k$ colours and take a smallest such map, so that every country borders at least $k - 1$ others — otherwise that country could be removed, the rest coloured, and the country put back in a spare colour. Replace each country by a corner and each shared border by an edge: the graph has $n$ corners, each of degree at least $k - 1$, drawn on the surface. The same two lines of counting bound its edges by $3(n - \chi)$, so the average degree is at most $6(1 - \chi/n)$, and $k - 1 \le 6(1 - \chi/n)$ with $n \ge k$ rearranges to Heawood’s expression. The floor on corners and the ceiling on colours are one inequality read in two directions.

To show that many colours are ever needed, one has to find a map in which that many countries all touch each other — which is the dual of a triangulation, or a near-triangulation, whose corners are all joined: the complete graph drawn on the surface. So the two questions, fewest corners and most colours, are both questions about the largest complete graph a surface can hold, and Gerhard Ringel and Ted Youngs’s proof in 1968 that Heawood’s colour bound is right for every surface but one was a proof, surface by surface, that those complete graphs can be drawn.

The one exception to the colouring theorem is the Klein bottle. Heawood’s formula says seven, and Philip Franklin showed in 1934 that six always suffice there. That is the same fact as the Klein bottle’s exception below: seven countries all touching each other would be a seven-corner triangulation turned inside out, and there is none.

Six corners for the projective plane #

The projective plane — a disc sewn to a Möbius band, the smallest one-sided closed surface — meets its floor of six. The drawing is a disc whose opposite rim points are the same point. Five triangles fan round the centre; five thin ones run from the pentagon’s edges to the rim, each with its tip opposite a pentagon corner and carrying that corner’s label, which is what makes the gluing of opposite rim points consistent. Ten triangles, fifteen edges, six corners, and every pair of corners joined.

It is the icosahedron folded in half. An icosahedron’s twelve corners come in six opposite pairs and its twenty triangles in ten; identify each point with its opposite and the result is this triangulation. Unlike the torus, it cannot be built out of flat triangles in space without crossings, since no one-sided closed surface can be placed in space without passing through itself — the same obstruction as the Klein bottle’s.

The Klein bottle that seven corners cannot make #

Heawood’s floor for the Klein bottle is seven, the same as the torus’s, because the two have the same characteristic. The counting cannot tell them apart. The question is whether seven corners, twenty-one edges and fourteen triangles can be arranged into a one-sided surface instead of a two-sided one, and the counting has nothing more to say.

A search can say it. With seven corners there are thirty-five possible triangles, and the question is which sets of fourteen of them close up into a surface: every one of the twenty-one edges bordering exactly two, the triangles round every corner closing into a single disc. The search builds such a set one triangle at a time, always completing the edge that has fewest ways left to be completed, and abandons any branch that puts an edge into three triangles.

The search finds 120 surfaces on seven labelled corners, every one of them a torus, and not one Klein bottle. The hundred and twenty are all the seven-corner torus relabelled: there are $7! = 5{,}040$ ways to label seven corners, and the torus has forty-two symmetries — the maps $i \mapsto ai + b$ modulo $7$ — so $5{,}040 / 42 = 120$ different labelled copies. The figure checks all three numbers, and checks that the twelve six-corner surfaces are likewise one projective plane under its sixty symmetries. The Klein bottle needs eight corners, and the proof that seven cannot work is the empty column.

This is Franklin’s theorem reached by exhaustion rather than argument, and it is worth being clear about what the search proves. It is not a sample, and it does not depend on the search being clever: every set of triangles that could possibly close up is either tried or ruled out because one of its edges was already full. The absence it reports is an absence from a complete list.

One more corner #

Seven corners give one torus and no Klein bottle. The obvious next question is what an eighth corner buys, and the same search, run on eight corners, answers it — with one change that keeps it exhaustive. At eight corners Heawood’s count asks for twenty-four edges out of twenty-eight pairs, so a triangulation need not use any particular edge. But every triangulation has some triangle, and relabelling can always make that triangle $\{0, 1, 2\}$. So the search starts from that triangle, closes open edges as before, and sorts what it finds into types by relabelling.

Eight corners carry seven different tori and six different Klein bottles. The count agrees with Frank Lutz’s published census of small triangulated surfaces, and the figure carries its own check on the search: a type with $s$ symmetries has $8!/s$ labellings, and the fraction of them that contain the triangle $\{0, 1, 2\}$ must be exactly the fraction of the fifty-six possible triangles that are used, sixteen in fifty-six. The number of times the search met each type matches that prediction for all thirteen, which is how one knows it neither missed a labelling nor met one twice.

The table has a pattern worth noticing. The torus’s types are more symmetric than the Klein bottle’s: the most symmetric eight-corner torus has thirty-two symmetries, while the most symmetric Klein bottle has eight, four have only two, and one has none beyond the identity. Symmetry is a constraint, and the one-sided surface, which cannot be consistently oriented, has fewer ways to be symmetric. So although the torus has more types, the Klein bottle has more labellings — each type is spread across more relabelled copies because fewer relabellings leave it unchanged.

The jump from none to six is also a lesson about the floor. At seven corners the complete graph is forced and the Klein bottle cannot hold it; at eight, four pairs of corners are allowed to stay unjoined, and that slack is enough. The exception is not a sign that the Klein bottle is expensive in general — it is cheap, like every surface of characteristic zero — but that it cannot be perfectly efficient, with every pair of corners adjacent.

The other two exceptions #

The remaining exceptions sit further down the chart, and neither is small enough for this search. The surface with three cross-caps, characteristic $-1$, has floor eight and needs nine; Ringel proved in 1955 that it and the Klein bottle are the only one-sided surfaces that miss the floor. The surface with two handles, characteristic $-2$, has floor nine and needs ten; Mark Jungerman and Ringel completed the two-sided case in 1980, showing that it is the only two-sided surface that misses. Every other closed surface can be triangulated with exactly Heawood’s number of corners.

The two-handled surface’s exception is the harder one to see, because at nine corners the floor does not demand the complete graph — thirty-three edges are needed out of thirty-six pairs, so three pairs of corners may stay unjoined and there is slack. What fails is not visible in any count. The proof is a case analysis of how those three missing edges can sit, and computer enumerations of small triangulations have since confirmed it.

What the figures cannot show #

The searches stop at eight corners. Each more corner multiplies the work many times over, and the two-handled surface’s exception, at nine and ten corners with characteristic $-2$, is a search many thousands of times larger. Those two exceptions are quoted here, not found.

The drawings are flat pictures of surfaces that are not. The torus is drawn unrolled and the projective plane with its rim glued in the reader’s imagination. Császár’s polyhedron puts the torus in space; the projective plane cannot be put there at all.

And the floor is a statement about corners only. Among triangulations with the fewest corners there can be many different ones, and the count of them — how many distinct minimal triangulations a surface has — grows quickly with the number of handles and is known only for small cases.

Still open: how many minimal triangulations #

Surfaces have now been classified, the classification proved, boundary added, gluings counted, random gluings measured, surfaces cut into their smallest pieces and built from the fewest corners. What has not been done is to put a geometry on them: the pants decomposition’s lengths and twists are the coordinates of that, and which shapes a surface can take is a subject of its own.

The counting question that stays open is the one the eight-corner table begins. For every surface except the three exceptions there is a triangulation with exactly Heawood’s number of corners, but how many there are — how many distinct ways the complete graph, or nearly the complete graph, can be drawn on a surface as a triangulation — is known only in special families, where it grows faster than any exponential in the number of corners. The colouring half of this essay is the four-colour problem’s easier cousin on every other surface, and the one-sided surfaces that refuse to sit in space are the Klein bottle’s problem again.

What is worth carrying away #

A counting argument gives a floor, and a floor is not an answer until something meets it. For corners on a surface, the floor is met almost everywhere, and the three places it is not are exactly the places where the counting’s one assumption — that the edges can all be realised at once — fails for a reason the counting cannot see.

The habit worth keeping is to check a bound against a search while the cases are small enough to search. Heawood’s inequality treats the torus and the Klein bottle as the same surface, and only a complete list of seven-corner surfaces shows that one of them is built and the other is not.