Sperner's Lemma

Three colors on a triangulated triangle force a fully colored cell.

The idea

Triangulate a triangle: cut it into small triangular cells that tile it, any two cells meeting along a whole shared edge, at a single shared vertex, or not at all. Then color every vertex of the triangulation with one of the labels $1$, $2$, $3$, obeying two boundary rules: the three corners of the big triangle receive three different colors, and every other vertex on a side of the big triangle receives one of the two colors sitting at that side's ends. Vertices interior to the big triangle may receive any of the three colors. Such an assignment is a Sperner coloring, and a cell whose three vertices carry all three colors is fully colored.

Theorem (Sperner's lemma).

Every Sperner coloring of every triangulation of a triangle contains an odd number of fully colored cells. In particular, it contains at least one.

The figure shows a Sperner coloring of a small triangulation, with a fully colored cell shaded.

The strength of the lemma is how little it assumes. The cells may have any sizes and shapes, the triangulation may be as fine as desired, and the interior colors are completely unrestricted: the two boundary rules alone force a fully colored cell to appear.

Ways to work on it

• Walkthrough. Check a small colored triangulation against Sperner's rules, then find the cells showing all three colors.
• Proof. Prove Sperner's lemma by a parity count of the doorways between cells.
• Practice. Count the color changes along one side of a Sperner-colored triangle.
• Hardest. Decide what the boundary of a Sperner coloring forces inside, sight unseen.

Not sure where to start? Take the ten-question placement test.