Definition

(In the sample diagram both index I and content C equal -1.)

The Index Lemma

The index equals the content.

Proof

For the proof let S be the number of edges labeled AB on and inside the polygon counted in the following way: each triangle is considered apart from all the others and its edges AB counted +1 or -1 by orientation. The proof is completed by showing that C = S = I. To prove the first equality, consider a complete triangle of type ABC. This has just one edge of positive orientation and so contributes +1 to S. At the same time as a complete triangle it counts +1 as part of C. As a second example consider a triangle of type ABA. This has two edges AB, one each of positive and negative orientation, and so contributes a total of 0 to S. It also contributes zero to C, since it is not complete. By surveying all the possible types of triangle, one verifies that each triangle is counted in the same way in S as in C; therefore C = S.

On the other hand, consider an individual edge labeled AB. If this edge is inside the polygon, then it is an edge in two triangles in one of which it counts plus one while in the other it counts minus one. These edges then contribute nothing to S. But edges on the boundary of the polygon are counted only once in S, and then just as they are for the index I. Therefore S = I.

For now, let's use the Index Lemma to prove first Sperner's Lemma and then Brouwer's Fixed Point Theorem. In the following we shall only consider triangulations of triangles and not of arbitrary polygons. Thus consider a triangle D and triangulate it into smaller triangles. As before, label the vertices of the triangulation with the letters A, B, and C. We are interested in a particular kind of labeling.

Definition

A Sperner labeling of a triangle's triangulation is a labeling that satisfies the following conditions:

1. The vertices of the original triangle are labeled with three different letters A, B, and C.
2. Vertices of the triangulation that lie on the side AB are labeled either A or B. A similar condition holds for the vertices on sides BC and AC.
3. There is no restriction on labeling of the vertices of the triangulation inside the original triangle.

Sperner's Lemma

Every Sperner's labeling contains at least one complete triangle.

Remark

To better appreciate the proof or, perhaps, even to come up with a different one, it may be useful to gain insite into the dynamics of labeling as one keeps adding nodes to the triangulation. In the applet below you add nodes by clicking inside (or on the side of) the original triangle. The new node is labeled according to which of the radio buttons is checked. The labeling can be changed later by repeatedly clicking on existing nodes.

Proof of Sperner's Lemma

We shall actually show that the number of complete triangles is odd. From the Index Lemma suffice it to show that the Index I in Sperner's triangulation is odd. With this in mind we ought only to consider the side AB of the original triangle. Let's call a segment complete if its ends are labeled differently, i.e. A and B. Let b stand for the number of complete segments on the side AB of the original triangle. Let a denote the number of AA segments, and let c denote the number of internal (to the side AB) A vertices. Thus, e.g. the total number of A vertices on the side AB of the original triangle is c+1. Since, each AA segment contains two A vertices while each AB contains only one, and every internal A vertex is shared by two segments of the subdivision, we have 2a + b = 2c + 1. Therefore b is odd.

Brouwer's Fixed Point Theorem

Let f be a continuous transformation of a triangle into itself. Then there exists a point P such that P = f(P).

Remark

Definition

The longest edge of a triangulation T is called its diameter d(T).

Proof

Thus let D be a triangle, and f:DD a continuous transformation of D into itself. For every PD form v(P)=f(P)-P, a vector from P to f(P).

For simplicity, position D such that its base is horizontal and the third vertex is located above the base. Next we shall consider a sequence of triangulations T_n of D with d(T_n) decreasing to 0 as n growth. With each such triangulation we associate a Sperner's labeling. A vertex P of the triangulation receives a label A iff v(P) points in the northeast or east direction, it receives a label B if v(P) points in the northwest or plain west direction; for a strictly north direction select either A or B randomly. All other P's are labeled with C.(Why is this a Sperner's labeling?) Of course, if v(P)=0 we have a problem with our labeling. But, if we ran into a point P where v(P)=0 we may stop here since then f(P)-P=0 and P is the fixed point of f. Thus assume that this has not happened. Then the triangulation T_n is assured to have a complete triangle D_n.