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:
“Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
—Henry David Thoreau (1817–1862)
“a meek humble Man of modest sense,
Who preaching peace does practice continence;
Whose pious life’s a proof he does believe,
Mysterious truths, which no Man can conceive.”
—John Wilmot, 2d Earl Of Rochester (1647–1680)
“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)