Sperner's lemma
From Academic Kids

In combinatorial mathematics, Sperner's lemma states that every Sperner coloring of a triangulation of an ndimensional simplex contains a cell colored with a complete set of colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points, and in rootfinding algorithms.
According to the Soviet Mathematical Encyclopaedia (ed. I.M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) has also become known as the Sperner lemma  this point is discussed in the English translation (ed. M. Hazewinkel).
Contents 
Twodimensional case
The twodimensional case is the one referred to most frequently. It is stated as follows:
Given a triangle ABC, and a triangulation T of the triangle. The set S of vertices of T is colored with three colors in such a way that
 A, B and C are colored 1, 2 and 3 respectively
 Each vertex on an edge of ABC is to be colored only with one of the two colors of the ends of its edge. For example, each vertex on AC must have a color either 1 or 3.
Then there exists a triangle from T, whose vertices are colored with the three different colors.
Multidimensional case
In the general case the lemma refers to a ndimensional simplex
 <math>\mathcal{A}=A_1 A_2 \ldots A_{n+1}<math>.
We consider a triangulation T which is a disjoint division of <math>\mathcal{A}<math> into smaller ndimensional simplices. Denote the coloring function as f : S → {1,2,3,...,n,n+1}, where S is again the set of vertices of T. The rules of coloring are:
 The vertices of the large simplex are colored with different colors, i. e. f(A_{i}) = i for 1 ≤ i ≤ n+1.
 Vertices of T located on any given kdimensional subface
 <math>A_{i_1}A_{i_2}\ldots A_{i_k}<math>
 are colored only with the colors
 <math>f(A_{i_1}),f(A_{i_2}),\ldots,f(A_{i_k})<math>.
Then there exists a simplex from T, whose vertices are colored with all n+1 colors.
Proof
We shall first address the twodimensional case. Consider a graph G built from the triangulation T as follows:
 The vertices of G are the members of T plus the area outside the triangle. Two vertices are connected with an edge if their corresponding areas share a common border, which is colored 12.
Note that on the interval AB there is an odd number of borders colored 12 (simply because A is colored 1, B is colored 2; and as we move along AB, there must be an odd number of color changes in order to get different colors at the beginning and at the end). Therefore the vertex of G corresponding to the outer area has an odd degree. But it is known that in a finite graph there is an even number of vertices with odd degree, and therefore there is an odd number of vertices with odd degree corresponding to members of T.
It can be easily seen that the only possible degree of a triangle from T is 0, 1 or 2, and that the degree 1 corresponds to a triangle colored with the three colors 1, 2 and 3.
Thus we have obtained a slightly stronger conclusion, which says that in a triangulation T there is an odd number (and at least one) of fullcolored triangles.
A multidimensional case can be proved by induction on the dimension of a simplex. We apply the same reasoning, as in the 2dimensional case, to conclude that in a ndimensional triangulation there is an odd number of fullcolored simplices.
External link
 Sperner's Lemma (http://www.cuttheknot.org/Curriculum/Geometry/SpernerLemma.shtml) (Java)
Categories: Combinatorics  Topology  Lemmas  Proofs