Introduction

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.

Find the Rainbow Triangle

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.

<!-- Sperner’s Lemma demo — color vertices, find rainbow triangles -->
<p class="hint">Click any unlocked vertex to cycle its color. Corner vertices are fixed. Edge vertices follow Sperner’s boundary rule (two colors only). A rainbow triangle (all three colors) is guaranteed to exist — try to avoid it!</p>
<div id="canvas-wrap">
  <canvas id="tri-canvas" width="380" height="340"></canvas>
</div>
<div class="status" id="status">Click vertices to change colors.</div>
<div class="btns">
  <button id="btn-find" type="button">Highlight rainbow triangles</button>
  <button id="btn-reset" type="button" class="ghost">Reset colors</button>
</div>

/* Sperner demo styles */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Sperner’s Lemma interactive demo
// Rule: color vertices with 3 colors; corners get one each; boundary vertices use only their edge’s two colors.
const COLORS = ['red','green','blue'];
const COLOR_FILL = ['#e63946','#2a9d3a','#1d6fbf'];
const COLOR_STROKE = ['#a01020','#1a6b28','#114e8c'];
const RAINBOW_HIGHLIGHT = '#f4d03f'; // gold highlight for rainbow triangles

// Triangulation grid depth N — the big triangle is split into N^2 small triangles
// A depth-4 grid gives 16 upward + 12 downward = 28 small triangles and 15 vertices.
const N = 4; // depth of triangulation

// Build vertex list in row-major order: row 0 has 1 vertex, row 1 has 2, etc.
// Each vertex stores its grid position, pixel coords, color index (-1 = unset), and locked flag.
function buildVertices() {
  const verts = [];
  // Triangle apex at top-center; bottom-left = green; bottom-right = blue; top = red.
  const cx = 190, cy = 320, side = 340;
  const dx = side / N;
  const dxhalf = dx / 2;
  const dy = (side * Math.sqrt(3) / 2) / N;
  for (let row = 0; row <= N; row++) {
    for (let col = 0; col <= row; col++) {
      const x = cx - row * dxhalf + col * dx;
      const y = cy - row * dy;
      verts.push({ row, col, x, y, color: -1, locked: false });
    }
  }
  return verts;
}

// Flat index for (row, col) — row r has r+1 vertices starting at r*(r+1)/2.
function idx(row, col) { return row * (row + 1) / 2 + col; }

// Build all small triangles: each row produces upward and downward triangles.
function buildTriangles(verts) {
  const tris = [];
  for (let row = 0; row < N; row++) {
    for (let col = 0; col <= row; col++) {
      // upward-pointing triangle
      tris.push([idx(row,col), idx(row+1,col), idx(row+1,col+1)]);
      if (col < row) {
        // downward-pointing triangle
        tris.push([idx(row,col), idx(row,col+1), idx(row+1,col+1)]);
      }
    }
  }
  return tris;
}

const verts = buildVertices();
const tris = buildTriangles(verts);

// Initialize Sperner coloring: lock the three corners with distinct colors.
// Corner rule: top=red(0), bottom-left=green(1), bottom-right=blue(2)
verts[idx(0,0)].color = 0; verts[idx(0,0)].locked = true;  // top corner: red
verts[idx(N,0)].color = 1; verts[idx(N,0)].locked = true;  // bottom-left corner: green
verts[idx(N,N)].color = 2; verts[idx(N,N)].locked = true;  // bottom-right corner: blue

// Allowed colors for each vertex based on Sperner’s boundary rule.
function getAllowedColors(v) {
  const { row, col } = v;
  const isTopLeft = (col === 0 && row > 0 && row < N);   // left edge: between top(red) and bottom-left(green) => allowed red,green
  const isTopRight = (col === row && row > 0 && row < N); // right edge: between top(red) and bottom-right(blue) => allowed red,blue
  const isBottom = (row === N && col > 0 && col < N);     // bottom edge: between bottom-left(green) and bottom-right(blue) => allowed green,blue
  if (isTopLeft) return [0, 1];   // top-left edge: red or green
  if (isTopRight) return [0, 2];  // top-right edge: red or blue
  if (isBottom) return [1, 2];    // bottom edge: green or blue
  return [0, 1, 2]; // interior vertex: any color
}

// Initialize non-locked vertices with first allowed color.
verts.forEach(v => {
  if (!v.locked) {
    const allowed = getAllowedColors(v);
    v.color = allowed[0];
  }
});

const canvas = document.getElementById('tri-canvas');
const ctx = canvas.getContext('2d');
let rainbowTris = [];

// Find all rainbow triangles (triangles with all 3 distinct colors on vertices).
function findRainbow() {
  rainbowTris = tris.filter(t => {
    const cs = new Set(t.map(i => verts[i].color));
    return cs.size === 3;
  });
  return rainbowTris;
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  findRainbow();

  // Draw each small triangle; fill rainbow ones in gold.
  tris.forEach(t => {
    const isRainbow = rainbowTris.includes(t);
    const [a, b, c] = t.map(i => verts[i]);
    ctx.beginPath();
    ctx.moveTo(a.x, a.y); ctx.lineTo(b.x, b.y); ctx.lineTo(c.x, c.y);
    ctx.closePath();
    ctx.fillStyle = isRainbow ? RAINBOW_HIGHLIGHT : '#f0f4f8';
    ctx.fill();
    ctx.strokeStyle = '#8a9ab0';
    ctx.lineWidth = 1;
    ctx.stroke();
  });

  // Draw each vertex as a colored circle; locked corners get a thicker border.
  verts.forEach(v => {
    ctx.beginPath();
    ctx.arc(v.x, v.y, v.locked ? 9 : 8, 0, Math.PI * 2);
    ctx.fillStyle = COLOR_FILL[v.color];
    ctx.fill();
    ctx.strokeStyle = COLOR_STROKE[v.color];
    ctx.lineWidth = v.locked ? 2.5 : 1.5;
    ctx.stroke();
  });

  updateStatus();
}

function updateStatus() {
  const s = document.getElementById('status');
  const count = rainbowTris.length;
  if (count === 0) {
    s.textContent = 'No rainbow triangle yet — keep trying!';
    s.className = 'status info';
  } else {
    s.textContent = fmt(count === 1 ? '%count% rainbow triangle found (gold). Sperner’s lemma holds!' : '%count% rainbow triangles found (gold). Sperner’s lemma holds!', { count: count });
    s.className = 'status ok';
  }
}

// Click nearest vertex within 22px to cycle its allowed colors.
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const mx = (e.clientX - rect.left) * scaleX;
  const my = (e.clientY - rect.top) * scaleY;
  let nearest = null, best = Infinity;
  verts.forEach(v => {
    const d = Math.hypot(v.x - mx, v.y - my);
    if (d < best) { best = d; nearest = v; }
  });
  if (nearest && !nearest.locked && best < 22) {
    const allowed = getAllowedColors(nearest);
    const cur = allowed.indexOf(nearest.color);
    nearest.color = allowed[(cur + 1) % allowed.length];
    draw();
  }
});

// Highlight rainbow triangles button handler.
document.getElementById('btn-find').addEventListener('click', () => {
  const rb = findRainbow();
  if (rb.length === 0) {
    const s = document.getElementById('status');
    s.textContent = 'No rainbow triangle yet — keep trying!';
    s.className = 'status info';
  }
  draw();
  console.log('Rainbow triangles found:', rb.length);
});

// Reset all non-locked vertices to first allowed color.
document.getElementById('btn-reset').addEventListener('click', () => {
  verts.forEach(v => {
    if (!v.locked) {
      const allowed = getAllowedColors(v);
      v.color = allowed[0];
    }
  });
  draw();
});

draw();
Result
Console

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).

The Real Complexity

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.

Where It Matters

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 nn 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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sperner-lemma/Content licensed under CC BY-NC 4.0.