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.