Proof
We shall first address the two-dimensional 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 with one endpoint colored 1 and the other colored 2.
Note that on the interval AB there is an odd number of borders colored 1-2 (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 (the handshaking lemma) that in a finite graph there is an even number of vertices with odd degree. Therefore the remaining graph, excluding the outer area, has 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 full-colored triangles.
A multidimensional case can be proved by induction on the dimension of a simplex. We apply the same reasoning, as in the 2-dimensional case, to conclude that in a n-dimensional triangulation there is an odd number of full-colored simplices.
Read more about this topic: Sperner's Lemma
Famous quotes containing the word proof:
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)