12 pentagons!

I’ve been reading Sternberg’s “Group Theory and Physics”, Cambridge University, reprinted 1999. On pages 43 to 44 he says, “… every fullerene has exactly 12 pentagons. This is not an accident.”

The stable structure of carbon which has 60 carbon atoms arranged like the vertices of a soccer ball is called a buckyball. It turns out that, in similar structures, we can have any even number, greater than 18, of carbon atoms except for 22. This is equivalent to polyhedra having 12 pentagons and any number of hexagons except 1.

This family of structures consists of polyhedra whose faces are either pentagons or hexagons. In chemistry they are labeled by the number of carbon atoms, so they talk about

I find it unforgettable and marvelous that the number of pentagons is always exactly 12. And I can prove it.

Sternberg’s proof is somewhat different from mine, because I choose to use two general equations which we have seen before. One equation depends on the fact that every edge separates exactly 2 faces; the other depends on the fact that every edge joins exactly 2 vertices.

Imagine that we have a polyhedron. Choose one face, and count the number of edges it has. Do this for all the faces.

We will have counted each edge twice. Let be the number of faces with k edges; then, for example, is the number of pentagons. We have the general formula

.

(I think I first showed you that here.)

For example, the term says that we counted 3 edges for each triangular face we touched. But the 2e on the LHS says that we will have counted each of those edges as part of another face, too. And yes, an edge can join two different kinds of polygons.

Similarly, if we count the number of edges by counting the number at each vertex, we will have counted each edge twice. Let be the number of vertices with k edges; we have the formula

(I believe I have not shown you that equation, except in the very special case 2 e = 3 v, for triangulations.)

We also have Euler’s formula in general

and

in particular.

Let’s see what the smallest case looks like: 12 pentagons.

This is the dodecahedron, one of the five platonic solids. (Now is a good time to remark that people used to think of them as 3D solids, but for quite some time mathematicians have treated them as 2D surfaces bounding 3D volumes. Similarly, the sphere is the surface which bounds the ball.) We see that there are three edges at every vertex.

It has .

I note that it has 20 vertices. It corresponds to . That’s why the list starts at 20.

What about a soccer ball (buckyball)? Mathematica® knows this as the TruncatedIcosahedron.

It has . This corresponds to carbon 60. Or to the most common soccer ball. (Not all soccer balls have 32 faces, apparently.)

Note also that every vertex has 3 edges.

Not every polyhedron — not even every regular polyhedron — has 3 edges at every vertex. Here is the regular 20-sided Platonic solid, the icosahedron:

Incidentally, it has 5 edges at every vertex. We are going to assume 3 edges at every vertex.

Here is the question. If

• every face of a polyhedron is either a pentagon or a hexagon,
• and every vertex has three edges,

what are the possible polyhedra?

The answer has two parts:

• any such polyhedron must have 12 pentagons;
• it can have any number of hexagons other than 1.

What I will actually prove is that no number of pentagons is possible, except 12.

Our general formula for edges and faces

becomes

,

because for every other k.

Our general formula for edges and vertices becomes

because for every k ≠ 3.

The total number of faces f is

,

and the total number of vertices v is

.

Thus, we wish to investigate solutions of the following 4 equations:

.

It turns out that Mathematica® is extraordinarily cooperative if I write separate equations for

and consider a set of 5 equations:

When I tell it to eliminate , Mathematica® tells me that :

It’s not too difficult to work this out by hand; you can do it without Mathematica.

This algebra places no restrictions on the number of hexagons. An it’s easy enough to exhibit solutions for any number of hexagons. Even for just one hexagon! Ruling out that case is a challenge; the proof dates only from 1963.

We know a couple of cases. We know that (no hexagons) is a dodecahedron. And (32 faces total) is a soccer ball or buckyball.

Whether or not we can actually build a polygon with any value of is another question. It turns out that there is only one nonnegative value of which does not work: we can’t have just one hexagon.

We can have a polyhedron with any number except n=1; that is, only cannot exist. But i haven’t proved either that cannot exist, or that anything does exist, other than and , which I have drawn.

I am not about to try to prove either that cannot be constructed, or that every other value can be. Maybe someday, but not today. (Among other things, I have no idea if all the hexagonal faces can be chosen the same size, nor even if they are all regular hexagons. My geometric intuition is nil — but the algebra is clear. Well, maybe it isn’t: the algebra says that simply by counting vertices, edges, and faces we can rule out anything that doesn’t have 12 pentagons. It says northing about the shape or even about the existence.)

Exactly 12 pentagons. I think that is amazing. And the equations I used are nicely general, and can be used for other things – such as showing that there can be no regular polyhedra other than the 5 Platonic solids.

For more about buckyballs, you can try this Wikipedia article.

Here is a drawing that suggests why we can’t add just one hexagon to a dodecahedron.

Within my personal library, the best reference on polyhedra is Hartshorne’s “Geometry: Euclid and Beyond”. (See my bibliographies page.)

Ah, a book newly acquired since I drafted this is: Richeson, “Euler’s Gem”, Princeton University 2008; most of it should be accessible to a high school student.

My reference for the two “2 e” equations is Firby & Gardiner, also on my bibliographies page.

A proof that cannot exist can be found in Branko Grunbaum’s “Convex Polytopes”, Springer, 2nd Edition, 2003. (Also newly acquired. It’s a graduate text.)

Nonplanar graphs & the Euler characteristic

Introduction and K4, the complete graph on 4 vertices

I want to show you something clever, but I’m going to omit the details of how we justify part of it. And I’m going to raise a question about another part of it. But I think this application of the Euler characteristic is interesting, even if I won’t or can’t cross all the t’s.

We can define the Euler characteristic of a graph as . We can show, for example, that every tree (a graph with no closed paths) has . If a graph is not a tree, then the closed path might create a face, but we don’t count the faces.

One question that arises when we have a graph is: is the graph planar? That is, can it be drawn in the plane so that edges do not have extraneous intersections?

Better to show you. Draw a square (or rectangle), and draw the two diagonals. This is called K4, the complete graph on 4 vertices, because every vertex is connected to every other vertex.

But the diagonals cross each other.

But they don’t have to. Take one of them and stretch it, and pull it outside the square.

K4 is called a planar graph, because its edges can be laid out in the plane so that they do not cross. I might say that it’s manifestly planar. Its Euler characteristic is .

Although it has 3 faces, we aren’t counting them. (OTOH, it’s not an accident that it has 3 faces and its Euler characteristic is 1 – 3; I think each loop added to a tree subtracts 1 from the Euler characteristic.)

Now, the theorem I’m not going to prove (even Firby & Gardiner don’t prove all of it), is that if we embed a planar graph onto the sphere, and then count faces created by the embedding, the embedded graph has the Euler characteristic of the sphere:

We’re going to almost show that a couple of graphs cannot be planar; we will use to compute the number of faces created by the embedding, and we will show that either

is false.

Got that? I’m not going to prove that the Euler characteristic of the embedded graph is 2, but I’m going to use that result to compute the number of faces of a planar graph.

Why do I say embedding? Let’s look at K4, the square with diagonals: we have v = 4, e = 6, and we infer from that the embedded graph has 4 faces.

But when we drew the graph, it had 3 faces. Ah, but on the sphere there’s all the rest of the sphere, the “ocean” if you will. Note that the “ocean” touches 3 edges when I draw the graph so that it is manifestly planar. We’ve added a face when we embed the graph on the sphere.

So the Euler characteristic of a graph doesn’t count any faces; the Euler characteristic of a graph embedded on a surface does count faces.

Just for the fun of it: for K4, 2 e = 12, 3 f = 12, and we do have . In fact we have equality because every face has exactly 3 edges.

K5, the complete graph on 5 vertices

That was K4. Here is K5, i.e. 5 vertices and they’re each connected once to every other vertex:

Is it planar?

Embed it on the sphere. We have 5 vertices by definition, and (1/2) (5) (4) = 10 edges (“5 choose 2, order doesn’t matter”) From the Euler characteristic , we infer that the embedded graph has 7 faces. To be clear, if the graph K5 is planar, then the embedded graph has Euler characteristic 2 and 7 faces.

But we have

2 e = 20

and 3 f = 21,

and therefore 2 e < 3 f instead of .

We conclude that K5 cannot be planar.

(That inequality assumes that very face has at least 3 edges. Well, it can’t very well be a face with only 2 edges, can it? Can it?)

K3,3, the complete bipartite graph on 3 & 3 vertices

What about K3,3, the complete bipartite graph on 3 & 3 vertices? This is also called the utilities graph: we may imagine we have 3 utilities (gas, water, electric) and 3 houses, and every house needs to be connected to every utility. It’s called bipartite because there are two disjoint subsets of vertices, and all the vertices in one subset are connected to all the vertices in the second subset (and vice versa).

Is it planar? Can we lay out the utilities all on one level without the lines bumping into each other? (Of course, my electricity comes in on overhead wires, but in principle the town could have required that the electric line be underground, as the gas and water are.)

Here’s the graph:

Let’s check the same inequality, . We have 6 vertices and 9 edges. If the graph K3,3 is planar, then the embedded graph has Euler characteristic 2 and 5 faces… then 2e is 18, and 3f is 15, and the inequality is satisfied:

.

That tells us nothing.

Let’s think about it some more. Start at a vertex (“a”), follow an edge to a vertex (“b”) (which must be on the “other side”). If we return on the same edge, we don’t get a face. If we return on a different edge, we end up at a different vertex “c”. To get back to “a”, we have to go to the other side and back again.

That is, each face (except possible the “ocean”) has at least 4 edges. Let’s not worry about the ocean for now. If f3 = 0 (“no faces have 3 edges”), then we can show that

.

(The key is that every edge must separate two faces; then if every face has at least three edges,

where is the number of faces having i edges.

Now set f3 = 0, and replace :

since )

So we compute

2 e = 18 < 20 = 4 f,

instead of ,

and we conclude that K3,3 is not planar… except that we really need to argue that the ocean touches at least 4 edges.

Do we? If we suppose the ocean only touches 3 edges (i.e. f3 = 1), we can show that

.

But, instead, we have

2 e = 18 < 19 = 4 f – 1.

We still have a contradiction, so K3,3 is not planar.

It turns out, that’s all folks. Kuratowski’s theorem (1930) says that a graph is not planar if and only if it contains K5 or K3,3. They are the “atoms” of nonplanar graphs; at least one of them is contained in every nonplanar graph.

a distressing observation

Having done that, let me back up and confuse you. Let me show you the t’s I’m not crossing. (In addition to not proving that the Euler characteristic of the graph embedded on the sphere is 2.)

Let’s take a planar graph with 2 vertices and 1 edge, i.e. a single line segment. It’s the tree with 2 vertices. Embed it on the sphere, and infer that it has one face.

The ocean.

Which touches one edge.

Now, the ocean really seems to be a face, i.e. a 2D thing. But it only has 1 edge. Grrr. Did you believe me when I said that something couldn’t be a face if it only had two edges? That’s OK, I believed me, too.

Oh, don’t seriously think of checking

.

That came from the assumptions that every face has at least 3 edges (false), and every edge touches 2 faces (false, but close: in this case our single edge does have “ocean” on both sides).

We could also take a tree on 3 vertices, i.e. the previous graph with a vertex added inside the edge. Embed it on the sphere. Now we have 2 edges, 3 vertices, and we compute that it has 1 face, and that face touches all 3 vertices and both edges. But that face does not have 3 edges. I mention this case because the books limit the original theorem (“the Euler characteristic of a planar graph embedded on the sphere is 2″) to graphs with at least 3 vertices, which seems to include this case.

My objection in both of these cases is that the ocean is not a nice face. What we have not done for K5 or K3,3 is to show that there isn’t some weird shape of ocean that makes them planar but does not force the inequalities which we know are false.

Clearly, we would have to do some more work to make all of this hang together properly. What we’ve got is two really nice plausibility arguments that K5 and K3,3 are not planar.

When I check the graph theory books, they all seem to sail right past the number of edges on the ocean, and the requirement that every edge separates two faces. (Again, for these two trees, each edge does have a face on each side, but it’s the same face!)

References

Every one of the four graph theory books in the bibliography (Bollobas, both Bondy & Murty books, and Biggs, et al.) proves that K5 is nonplanar because it violates ; and also that K3,3 is nonplanar because it violates . Only Bollobas does not prove Kuratowski’s theorem. Biggs et al. contains Kuratowski’s paper.

Both Bondy & Murty books also prove that K5 and K3,3 are nonplanar because they violate the Jordan Curve theorem.

Finally, Firby & Gardiner, and Sieradski, prove that K5 is nonplanar because it violates , and they leave K3,3 to the exercises, without a hint.

The Euler Characteristic: Teasers

These are things i came across when I first started looking at the Euler characteristic, in fact, when I was looking at triangulations in particular.

n-manifolds

The Euler characteristic generalizes to dimensions other than 2, and there are at least three noteworthy theorems involving the Euler characteristic. I’m not going to say much about them, because they, like so much else, are still outside my comfort zone. I’ll just barely tell you what they are, and leave you to chase them down if they interest you.

As we’ve seen, the Euler characteristic of a polyhedron is given by

,

where v, e, f are the numbers of vertices, edges, and faces. Homeomorphic polyhedra have the same Euler characteristic, and that means we can define the Euler characteristic of a topological surface as the Euler characteristic of any polyhedron which is homeomorphic to it.

This alternating-sign sum of the numbers of 0-, 1-, and 2- simplices generalizes in the obvious way: for an n-simplex, we take the sum, with alternating signs, of the numbers of k-simplices, for k <= n. As for surfaces, so for n-manifolds: this is a topological invariant, and we want to define the Euler characteristic of an n-manifold as the Euler characteristic of any k-simplex homeomorphic to it.

But we’ve been told that topological, simplicial, and differential structures on manifolds do not always coincide for n > 3. We can define the Euler characteristic for k-simplices and for manifolds with simplicial structure, but I am going to look skeptically at the Euler characteristic of topological and differentiable manifolds until I learn more about the different structures.

BTW, we can go down a dimension, too: we can define the Euler characteristic of a graph as v – e.

Betti numbers

The Euler characteristic of an n-manifold has an extremely interesting equivalence: not only does the formula generalize from 2 to n, but it can also be generalized to a topological space X: we can write

where is the kth Betti number of X, and we assume that eventually (i.e. for k large enough) . (Lee, “Introduction to Topological Manifolds”; or Rotman, “An Introduction to Algebraic Topology”.)

But hold on just a minute. The Euler characteristic was defined for things with simplicial structure, and the Betti numbers are defined (not by me!) for topological spaces. But we know that simplicial & topological do not coincide for higher dimensions than 3, so we probably have to be rather careful here.

When all else fails, look carefully at the book. What we actually have is two definitions, a theorem, and an extension of the definition. We define the Euler characteristic of a simplicial complex, and the Betti numbers of a topological space; the theorem says that for a finite simplicial complex, the Euler characteristic is equal to the alternating sum of the Betti numbers:

Having the theorem, we then extend the definition of the Euler characteristic to any topological space: we define the Euler characteristic as the alternating sum of the Betti numbers; the theorem assures us that the two definitions of the Euler characteristic coincide on simplicial complexes.

We’re still not out of the woods. Looking in Rotman, I am reminded that there are different homology theories. Do they all give the same Betti numbers? I have no idea. (Well, I suppose they do, but I’m ready for anything.) Gee, no wonder algebraic topology is still on my list of things to study.

As an aside, in Massey’s combined book, “A Basic Course in Algebraic Topology”, I find a note which says that until about 1930, mathematicians focused on the Betti numbers (and the torsion coefficients) of homology groups, rather than on the groups themselves.

Index of a surface

Next, on this detour, we have the Poincare-Hopf index theorem, which says that the Euler characteristic of a surface is equal to the index of the surface.

Hey what?

As the Betti numbers came out of left field, the study of vector fields on a surface is coming out of right field. If you’ve ever been told that you can’t comb the hair on a ball, you’ve encountered one of the key theorems of the subject.

There are two ways to look at the index theorem. In the special setting of dynamical systems (i.e. differential equations), we are looking at points where the vector field vanishes (critical points, which are equilibrium points, but not necessarily stable equilibria). More specifically, we are interested in the flow pattern in the vicinity of critical points.

In this context, we break flow patterns into sectors each of which is called parabolic, hyperbolic, or elliptic; and we have a recipe (due to Bendixson) for planar systems which says that the index of a critical point (wrt the vector field) is

I = 1 + (e-h)/2,

where e and h are the numbers of elliptic and hyperbolic sectors. (The parabolic sectors don’t contribute to the index.)

The index of the surface wrt the vector field is the sum of the indices of the critical points. The Poincare-Hopf theorem says that the

index of the surface (in fact, of an n-manifold) wrt the vector field is equal to the Euler characteristic of the manifold.

(I believe that Poincare proved it for surfaces and Hopf extended it to higher dimensions. I am not sure that the definition of sectors applies in higher dimensions; that is, I am not sure how the index is defined in higher dimensions.)

This imposes significant constraints on the possible vector fields.

That’s one way to do it. My references for this approach are Perko, “Differential Equations and Dynamical Systems” and Firby & Gardiner, “Surface Topology”.

I was hoping to at least construct illustrations of the three kinds of sectors, but I’m finding it difficult and very annoying to update my version 5 drawings to version 6 of Mathematica®. (Backwards compatibility? What’s that?)

From Firby & Gardiner, I extract the following description. A sector is parabolic if all paths lead to the critical point, or all paths lead away. A sector is elliptic if all paths begin and end at the critical point. A sector is hyperbolic if all paths sweep past the critical point.

But there is another way to define and compute the index of a critical point. In fact, we can compute the index of any point wrt a curve, but if it’s not a critical point, then its index is zero; therefore we can confine our attention to critical points. This approach starts with winding numbers. Fulton, “Algebraic Topology: A First Course”, is excellent for surfaces (with multiple chapters on winding numbers and vector fields), and even suggests how to generalize to higher dimensions. Also, Sieradski, “An Introduction to Topology and Homotopy”, has a few sections, rather than chapters, on winding numbers and vector fields.

I’m beginning to look forward to tackling Fulton.

Gauss-Bonnet

The Gauss-Bonnet theorem, as O’Neill states it (“Elementary Differential Geometry”) says that the gaussian curvature, integrated over all of a compact orientable surface, is equal to , where is the Euler characteristic of the surface.

Oh, but doesn’t that require differentiable structure?

Yes and no.

Bloch shows us the Gauss-Bonnet theorem for simplicial surfaces! It turns out we can associate curvature with the vertices of a simplicial surface, in such a way that the total curvature (the sum of the curvatures at each vertex) is equal to .

I’ll talk about this when I discuss chapter 3 of Bloch. I finished the chapter eons ago, but I haven’t tallied it up yet.

The Euler characteristic (triangulations 2)

I want to talk about some things I saw when I was looking at triangulations. This also continues my reading in Bloch.

The major thing I saw was the Euler characteristic. We usually define it for polyhedra, as the alternating sum / difference of the number of vertices, edges, and faces (0-, 1- and 2- simplices)…

Then we would define it for a surface by taking the Euler characteristic of any polyhedron which is homeomorphic to that surface.

For that to be well-defined, of course, requires that all polyhedra which are homeomorphic to a surface S have the same Euler characteristic (as they do).

By the same token, we could define the Euler characteristic of a surface from any triangulation of the surface, after we show that all triangulations of a surface have the same Euler characteristic. Oh, and we’d better actually prove that every topological surface (every topological 2-manifold) can be triangulated.

Yes, they can be. Not true for topological 4-manifolds, and I think it’s still wide open for higher dimensions. In contrast, I believe that every differentiable n-manifold supports a unique piecewise linear (PL) structure (which is the generalization, they tell me, of triangulations).

Details.

So we have the Euler characteristic in one hand. With the other hand, let’s grab the classification theorem. One form said that every compact connected surface is a connected sum of tori T or of projective planes P:

gT, g = 0,1,2,3…

or

gP, g = 1,2,3,…

(where the sphere is 0T, the “torus” with no holes; 2T = T#T, etc., and the integer g is called the genus of the surface.)

Is there any chance we can easily compute the Euler characteristic of the connected sum A#B from the Euler characteristics of A and B? If we could, then we could compute the Euler characteristic of nT and nP, hence of all connected compact surfaces.

Of course we can, and here’s the equation:

Oh, now go get the Euler characteristics of triangulations of the sphere, torus, and projective plane.

Ok, we can do that.

But it would be simpler to get the Euler characteristic from the polygonal disks from which we constructed the basic surfaces. We would have to know that counting the v, e, f (after identifications) of the polygonal disk gives us the same answer, but it does.

Yes, having specifically studied Bloch because he distinguished topological surfaces from simplicial surfaces, I am now effectively going to compute the Euler characteristics of topological surfaces instead of simplicial surfaces.

I never said I didn’t want to mix it all together; I just wanted to see the separate ingredients that went into the stew.

In principal we only need 3 surfaces: sphere, torus, and projective plane. Nevertheless, since the Klein bottle has an equally simple polygonal disk, I’ll show it too. One set of representations is

Edges which are to be identified (“glued”) have the same symbol; an arrow shows the directions which are used. Points which are to be identified have the same color. I considered using colors for the edges, but we can actually do algebra with the symbols: the sphere can be called , the torus , etc.) If it helps, the colors of the vertices are a consequence of the identifications of the edges.

From them, we compute that the Euler characteristics are

Note that the largest Euler characteristic is 2, and it corresponds to a sphere. Note that all four are non-negative. Note that an Euler characteristic of 1 corresponds to the (non-orientable) projective plane. Then for Euler characteristic of 0, we have two surfaces, one orientable, one not.

Then we compute that the Euler characteristic of gT is 2 – 2g, i.e. the set of even numbers less than or equal to 2. And the Euler characteristic of gP is 2 – g, i.e. the set of integers less than or equal to 1. (Maybe I should restrict g > 0 for nP, but I’m not sure it’s worth worrying about.) So if we have an odd negative Euler characteristic, the surface is unique and non-orientable; if the Euler characteristic is even and negative, there are two surfaces, one orientable, one not.

Note that all the new surfaces we construct have Euler characteristic less than zero.

Note that the connected sum of a sphere and any surface A has the same Euler characteristic as A. in fact, the connected sum is homeomorphic to A; gluing spheres to surfaces does not change them.

We know, however, another form of the classification theorem. The non-orientable surfaces gP can be written as a connected sum of tori plus either one projective plane or one Klein bottle:

mT#P

or

mT#K

for some m (and I am paying no attention to the relationships between these m’s and the genus g). To prove that, we need to know that

P # P = K

and

P # P # P = P # T.

We can now compute that the Euler characteristic of mT#P is (2 – 2m) + 1 – 2 = 1 – 2m, i.e. the set of odd integers less than or equal to 1.

The Euler characteristic of mT#K is (2-2m) + 0 – 2 = -2m, i.e. the set of even integers less than or equal to 0.

So, in fact, if the Euler characteristic is an odd negative, there is a unique surface of the form mT#P; if the Euler characteristic is even negative, there is an orientable surface of the form nT and a non-orientable surface of the form mT#K.

References for this material are

• Bloch, “A First Course in Geometric Topology & Differential Geometry”.
• Lee, “Introduction to Topological Manifolds”.
• Firby & Gardiner, “Surface Topology”.
• Massey, “Algebraic Topology: An Introduction” or “A Basic Course in Algbraic Topology”

See the bibliography.

Triangulations of Surfaces: minimum number of triangles

Edited 4 Sep. search on “edit”.

Take a cube. If you cut it along a few edges, you could lay it out flat. To restore the cube, we identify certain edges with each other. Similarly for a tetrehedron, or a theoretical soccer ball (with flat faces), or any polyhedron. For studying surfaces by looking at polyhedra (i.e. picewise linear structure), it is convenient to use only triangular faces (2D simplices) rather than arbitrary polygonal faces. The analog of our cut and flattened cube is called a triangulation. As before, we want to identify certain edges with each other.

In particular, the following

is offered as a triangulation of a torus (with the top & bottom edges identified, and the left & right, as we’ve seen before).

Why are there so many triangles? I have wondered that since the first time I saw it.

“Surely fewer would suffice,” I thought. Compared to the simple square which we use to generate a torus, that triangulation looks unnecessarily complicated.

Yes, it is, but not by much. It is true that fewer would suffice, but not a whole lot fewer.

I could hand you the answer and be done with it. But I had fun chasing this down and saw many things along the way. It was a fine little gambol through the park.

On second thought, this post is getting way too long, so I’d better hand you the answer and save the cultural remarks for another post.

Back up a moment. What exactly is the question?

I’m going to answer several questions.

• Why are there so many triangles in a triangulation of a torus?
• Is there a minimum number of triangles required in a triangulation of a torus?
• If so, what is it?
• Is there a minimum number of triangles required in a triangulation of any given surface?
• If so, is there a formula?
• If so, how do we derive it?

As I said quite a while ago, I wanted to get more comfortable with simplicial complexes; this took me into a bunch of algebraic topology books. While I was wandering and wondering, I came across this, in Rotman (Intro Algebraic Topology) p. 133, speaking of our picture: “This triangulation of the torus has 18 triangles…. It is known that the minimum number of triangles in a triangulation of the torus is 14 (see [Massey (1967), p. 34, Exercise 2] for an inequality implying this result.”

As I said, that triangulation is not much larger (18 triangles) than it needs to be (14 triangles), but it is way larger than I would have expected.

Come, Watson, the hounds are afoot.

Massey (Algebraic Topology, Introduction, p. 34 or A Basic Course… p. 31), exercise 2 is: “For any triangulation of a compact surface, show that”

1) 3 f = 2 e

2)

3)

where f, e, v are the numbers of triangles (= number of faces), edges, and vertices. (That appears to say there is a minimum number of triangles required for any triangulation of a given surface, including the torus, and we have a formula. Unfortunately, it does not quite stand by itself.)

You might want to scribble these down, with the numbers 1-3. For example, I’m generally going to refer to “Massey’s (3)” rather than display the inequality over and over again.

Ok. What’s the minimum number of triangles in a triangulation of the torus? We need the definition of the Euler characteristic

and we need to know that the Euler characteristic of the torus (T) is 0: .

While we’re at it, the Euler characteristic of the sphere is 2, of the projective plane is 1, and of the Klein bottle is 0. Yes, the Klein bottle and the torus have the same Euler characteristic. More on that in another post.

Now, Massey’s (3) implies that

.

For the minimum v = 7 we would have

Then

3 f = 2 e = 42, so f = 14.

That’s what Rotman told us. So there must be at least 14 triangles in a triangulation of the torus.

Now let’s start getting Massey’s formulae.

The first thing I did was observe that once we have the definition of , we can combine it with (1) to get (2).

So what about (1)?

Massey gives us the crucial property of a triangulation. Since a triangulation is homeomorphic to a surface, every point on it – including points on the “outside” edges, must be homeomorphic to a 2D disk. That means that the “outside” edges must be identified with other edges so that each of the “outside” edges is an edge of exactly two triangles (or two faces in general). Of course this also holds for the “interior” edges, which by construction are edges of exactly two triangles.

To put it another way, there cannot actually be any “outside” edges; they must all be interior.

That is, a triangulation is characterized by the fact that every edge is an edge of exactly two triangles. The formulae not withstanding, that may be the most important fact in this post. There is, however, another fact almost as important (later).

I like the way Firby & Gardiner do the next step. Suppose that what we have is a 2D complex – which may contain general polygons rather than just triangles – homeomorphic to a surface. That is, it may have faces with more than 3 sides. Instead of saying that every edge is the edge of exactly two triangles, we say that every edge is an edge of exactly two polygons.

We try to count the edges by counting faces. Let denote the number of faces with i edges. ( is the number of triangles, is the number of quadrilaterals, etc.) Then the weighted sum of faces

counts the number of edges associtaed with each face, but it counts them exactly twice because each edge is the edge of exactly two faces – that’s crucial. We have, then

If, now, there are only triangles , we get

i.e. Massey’s first equation

One down. and as I said, this equation and gives us the second equation (just eliminate f):

.

Two down, one to go.

Firby & Gardiner eventually state a theorem and a conjecture due to Heawood. The theorem is that if M is a compact surface with euler characteristic , then any map on M can be colored in no more than

colors. ( denotes the floor function, the largest integer less than or equal to x.) Note that the hypothesis of the theorem excludes the sphere ; and note that the number of colors required for a map on the sphere is the same for a finite rectangle in the plane. That is, Heawood did not prove the 4-color theorem.

The number h is called the Heawood number of the surface; the number of colors which suffice to color all maps on a surface is called the chromatic number of the surface.

And the number of vertices is bounded by the expression whose floor is the Heawood number. Hmm. This could be promising.

Heawood’s theorem says that if the Euler characteristic , then the chromatic number of a compact surface is its Heawood number.

Heawood’s conjecture was that the theorem was true for any : that the Heawood number is equal to the chromatic number for any compact surface. It is false, but just barely.

It turns out that there is exactly one exception to the conjecture: for the Klein bottle, the chromatic number is 6 while the Heawood number is 7. (The Heawood number for the sphere is 4; for the projective plane 6; and for the torus it’s the same as for the Klein bottle, 7, because they have the same , namely 0.)

edit:
The previous paragraph is correct. But my distinction between the Heawood conjecture and the Heawood theorem makes no sense. How can the theorem include when the counterexample is for ? The simplest correction might seem to be that the theorem is for , but even that isn’t right. (I think that correct would be the theorem as stated, but for orientable surfaces only.)

I based my summary on Firby & Gardiner, but I misread them. Upon review, I believe – they didn’t put it this way – that they said the theorem was that the chromatic number is less than or equal to the Heawood number for strictly less than zero; the conjecture, as I read them, is two generalizations: remove the restriction on , and replace the inequality by equality (chromatic number equal to Heawood number).

Unfortunately, I think their distinction is wrong, too. Now, I’m arguing about the history of mathematics, not the mathematics. I believe (Biggs et al.) that the theorem which Heawood stated in 1890 was: chromatic number equals Heawood number for orientable surfaces with . I’m not sure he proved it all, but I think that’s what he thought he was proving.

The Heawood theorem, as I see it, asserts that the chromatic number is equal to the Heawood number for orientable surfaces with . The conjecture would generalize that to all and to non-orientable surfaces. The Klein bottle, being non-orientable, is an exception – the only exception – to the conjecture, not to the theorem.
end edit

So the Heawood conjecture implied that the 4-color theorem was true (for the sphere, hence for the plane).

Back to Massey. The Heawood number occurs in map coloring…. but how do I get from it to vertices? Turns out I don’t. (Although I’m sure there’s a connection; I probably needed to read a couple of proofs.)

Fulton (Algebraic Topology First Course) gave me the last clue, on p. 115, problem 8.9. “Show that, for any triangulation of a sphere with g handles:”

1) 2 e = 3 f

2)

3)

I needed to have seen that

for a sphere with g handles, but I had. We’re looking at a special case of Massey’s (3).

Even though Fulton has asked for a special case, can we do the general case? No problem: the key is Fulton’s inequality (2).

Can we get Massey’s (3) from Fulton’s (2)? (You may very well have recognized (2) and said, “Oh, yeah!” Not me. My focus was on whether I could use Fulton’s (2) to get Massey’s (3)).

Piece of cake. Really. Consider it done.

Famous last words. It’s a piece of cake up to a point, and then it begins to look like cardboard instead of food. We’ll come to this. For now, assume we can get Massey’s (3) from Fulton’s (2).

Only then did I ask: can I prove Fulton’s (2)? I don’t know about you, but once I looked at (2) in its own right, it was crystal clear. This is the number of distinct pairs of v objects without repetition. Given a pile of vertices, v in number, choose one of them (v possible choices), choose a second one (v-1 choices), and divide by two because order is irrelevant.

That’s the maximum number of edges I can draw using v vertices, when loops and multiple edges are not allowed (the ends of an edge must be distinct, and no more than one edge may join two given vertices). I need not, however, draw all possible edges: the actual number e of edges is bounded above by the maximum number of edges, hence , so we have Fulton’s (2). QED.

So Massey’s inequality is far easier to obtain than any of the arguments concerning the Heawood number and map colorings. The Heawood number per se was interesting but apparently irrelevant.

So I thought. Then I figured I really ought to write out the derivation.

I learn so much when I look at the gory details.

From and , we get

.

From that and , we get

.

NOTE that the quadratic is always a parabola opening upward. It is negative between its two real zeroes, if they exist. So what we’ve actually shown is that the number of vertices must lie outside the two roots of that quadratic.

For the torus, , so we get . That quadratic has zeroes at v = 0 and v = 7, and we’re not going to allow negative numbers of vertices, so we assert that v must be 7 or more for a triangulation of a torus. That, we saw, required 14 triangles.

What about a sphere? , so we get . That quadratic has zeroes at 3 and 4…. Both are perfectly fine positive numbers, and in fact no positive integer is excluded by the quadratic bound.

As the dealer says in poker, “No help.” That quadratic inequality would not let us rule out 3 vertices or 2 or even 1. Something else must do that. My piece of cake is beginning to taste like cardboard.

Let’s recall Massey’s (1)

1) 3 f = 2 e

For both e and f to be positive integers, that equation requires a minimum of f = 2 and e = 3. OK, we can rule out 1 or 2 edges.

Is there something wrong with 3 edges?

Yes. Turns out there’s another fact we need.

Well, when we define a simplicial complex – which I know haven’t done – or when we imagine gluing triangles together, there are some obvious cases which we want to exclude. We don’t want one triangle partly inside another, and we also don’t want to share edges among too many triangles.

(I don’t know about your neighborhood, but in mine, houses are offset: i share a back fence with two neighbors, not one. We don’t want to allow that with triangulations.)

What your book says – whatever book you have – if it says this at all, is that if two triangles intersect at all, they intersect in either a vertex or an edge. The example they invariably draw shows 2 triangles having part of an edge in common. That’s a no-no.

But it’s also a no-no to have more than one edge in common. At least, I think so. I have not seen anyone emphasize that “an edge” excludes multiple edges, but it had better.

We know how to make a square into something homeomorphic to a sphere: glue the right edge to the top edge, and the left edge to the bottom edge. Fine, now imagine that we first put one diagonal inside that square, and then glue it that same way. What we get is still homeomorphic to a sphere; it looks like two triangles glued together on all three edges. It’s just not a triangulation because the two triangles do not intersect in an edge, but in 3 edges.

In short, the quadratic bound merely says that any integer number of vertices would work for a sphere, but 3 is too few to make a triangulation at all. Then the quadratic bound assures us that 4 should be allowed.

I should probably exhibit one such for both the sphere, but I’ll pass. I hope 4 vertices works, and i’ll leave it at that.

In summary,

• Why are there so many triangles in a triangulation of a torus? Because there can’t be any “outside” edges.
• Is there a minimum number of triangles required in a triangulation of a torus? Yes.
• If so, what is it? 14.
• Is there a minimum number of triangles required in a triangulation of any given compact surface? Yes.
• If so, is there a formula? Sort of: no less than 4, and no less than the larger root of a particular quadratic.
• If so, how do we derive it? Done.