Sperner's Lemma

Imagine a large triangle divided into many smaller triangles — a triangulation. Each vertex of this triangulation gets a color: red, green, or blue. There is just one rule, called the Sperner condition:

• The three corners of the big triangle get the three different colors (one each).
• Each vertex on an edge of the big triangle may only use one of the two colors assigned to that edge's endpoints.
• Vertices strictly inside the big triangle may receive any color.

Play by these rules however you like, and something remarkable is guaranteed: at least one small triangle will have all three colors — one red, one green, one blue vertex. This is Sperner's lemma, proved by Emanuel Sperner in 1928.

The result feels like a magic trick. No matter how cleverly you try to avoid it, a fully 3-colored cell — a rainbow triangle — must exist. And that unavoidable rainbow turns out to be the combinatorial heart of Brouwer's fixed point theorem and the existence of Nash equilibria in game theory.

The demo below shows a triangulated triangle. Click any vertex to cycle its color through red, green, and blue. The three corner vertices are pre-colored and locked. The boundary vertices may only use the two colors of their edge — the demo enforces this automatically.

<!-- {{c_html_comment}} -->
<p class="hint">{{hint_para}}</p>
<div id="canvas-wrap">
  <canvas id="tri-canvas" width="380" height="340"></canvas>
</div>
<div class="status" id="status">{{initial_status}}</div>
<div class="btns">
  <button id="btn-find" type="button">{{btn_find}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas-wrap { display: flex; justify-content: center; }
canvas { cursor: pointer; border-radius: 8px; max-width: 100%; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Every time you finish a valid Sperner coloring, the demo highlights the rainbow triangles in gold. Try to color the triangulation so that no rainbow triangle appears — you will find it is impossible. The lemma guarantees at least one always exists, and often there are several (always an odd number, in fact).

Sperner's lemma is a proved theorem — its truth is not in doubt. But the complexity question is: how hard is it to find the rainbow triangle?

The parity proof. Label each small triangle by the set of colors on its vertices. A fully 3-colored triangle is the only one with all three labels. Count the edges shared between any two triangles whose vertex-sets together contain all three colors. A careful parity argument shows this count is always odd — and in particular, non-zero. So a rainbow triangle must exist.

Path-following. There is a constructive proof: enter the big triangle through any boundary edge colored with two specific colors, then walk through the triangulation following a path that obeys a simple local rule. The path can never loop — it must eventually exit, and the exit point is a rainbow triangle. This "path-following" structure is at the heart of Lemke-Howson algorithms for Nash equilibria.

PPAD-completeness. Finding a Brouwer fixed point (which Sperner's lemma proves exists) is complete for the complexity class PPAD — Polynomial Parity Arguments on Directed graphs — introduced by Christos Papadimitriou in 1994. Problems in PPAD have solutions whose existence is guaranteed by a parity argument, but finding one can be as hard as any PPAD problem. This is believed to be strictly harder than polynomial time, though proving PPAD $\neq$ P remains open.

So Sperner's lemma sits in a subtle spot: its statement is an unconditional theorem, yet computing the witness efficiently is likely hard in general.

The rainbow triangle is not just a puzzle — it is a foundational tool:

• Brouwer's fixed point theorem: every continuous function from a convex compact set to itself has a fixed point. The standard combinatorial proof is a direct application of Sperner's lemma, using finer and finer triangulations whose rainbow cells converge to the fixed point.
• Nash equilibria: John Nash's proof that every finite game has a mixed-strategy equilibrium relies on Brouwer's theorem — and through it, on Sperner's lemma. Finding a Nash equilibrium is PPAD-complete, directly connected to the difficulty of locating rainbow triangles.
• Fair division and envy-free rent splitting: Francis Su's 1999 paper used Sperner's lemma to prove that $n$ roommates can always divide a house and set rents so that each prefers a different room and nobody envies another — a surprising application in economics.
• Computer graphics and mesh processing: triangulations are the backbone of 3D rendering; Sperner-style arguments appear in mesh refinement algorithms that must guarantee certain combinatorial properties.
• Topological data analysis: discrete Morse theory and persistent homology use triangulations and parity arguments that echo Sperner's proof.

Sperner's lemma is one of those results whose statement fits in a sentence but whose reach spans topology, economics, and complexity theory. Color a triangulation by three simple rules, and a rainbow triangle is guaranteed — no matter how hard you try to avoid it.

That guarantee is the combinatorial DNA of Brouwer's fixed point theorem and, through it, of Nash equilibria. Yet finding the rainbow triangle efficiently turns out to be as hard as the hardest problems in PPAD. A tiny coloring game hides one of the deepest questions about what can be computed quickly.