This is known as the Index Lemma, a fundamental result in the theory of Dynamic Systems and Algebraic Topology. The Lemma deals with triangulations of plane polygons. A triangulation of a polygon D is a division of D into a finite number of triangles so that each edge on the boundary of D belongs to just one triangle of the subdivision, and each edge in the interior of D is shared by exactly two triangles of the subdivision.
Consider a simple (with no self-intersections) polygon with an arbitrary number of vertices. Triangulate it in any way and label the vertices of the triangulation with the three labels A, B, and C. A triangle in a triangulation is called complete iff its three vertices all received different labels. It's natural to call a complete ΔABC. There are also triangles AAB, CCC, etc. Two quantities are associated with every triangulation.
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.
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.
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.
Here is another proof I learned from James Tanton.
Start with a triangulation of a sphere. Label all the vertices with one of three letters A, B, C. Then there is an even number of ABC triangles. For a proof, assume there is at least one ABC triangle. Place doors on AB edges and, starting with an ABC triangle form a path through the doors. The number of triangles is finite, meaning that somewhere, i.e., in one of the triangles, the path will have to terminate. The last triangle which obviously has only one AB edge must be labeled ABC. This could not be the original ABC triangle because the only way to get back there is through the door you already passed. However, this is impossible to step into a triangle twice. If it were possible, there would exist the first triangle twice traversed. This triangle would have to have three AB edges.
Remark
Such P is known as a fixed point of f. Therefore, the theorem claims that any continuous transformation of a triangle into itself has a fixed point. Let D be a triangle, g a continuous 1-1 transformation of D onto G. Then, for Q ∈ G we may define g(f(g-1(Q))) ∈ G. This gives us a continuous transformation of G into itself. If P is a fixed point of f and Q = g(P) then
g(f(g-1(Q))) = g(f(g-1(g(P)))) = g(f(P)) = g(P) = Q,
which exactly means that Q is a fixed point of thus defined transformation. The implication being that, although I have formulated Brouwer's Theorem for triangles only, it applies to a much wider class of planar sets. Loosely speaking, these are bounded closed sets with no holes.
We shall need the following
Definition
The longest edge of a triangulation T is called its diameter d(T).
Proof
Thus let D be a triangle, and f: D → D a continuous transformation of D into itself. For every P ∈ D 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 Tn of D with d(Tn) 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 Tn is assured to have a complete triangle Dn.
