Sperner's lemma

Builds on Simplicial complex Convex hull

Statement

Let $n \ge 1$ and let $\Delta$ be an $n$ -simplex in $\R^n$ with vertices $v_0, \ldots, v_n$ . Let $T$ be a triangulation of $\Delta$ by a finite simplicial complex. Let $\lambda$ be a colouring of the vertices of $T$ by $\set{0, 1, \ldots, n}$ . Assume the following for every set $S \subseteq \set{0, \ldots, n}$ . Each vertex of $T$ in the face $\operatorname{conv}\set{v_i : i \in S}$ of $\Delta$ has a colour in $S$ , where $\operatorname{conv}$ is the convex hull. Then the number of $n$ -simplices of $T$ whose vertices carry all $n + 1$ colours is odd; in particular there is at least one.

Remarks

The proof is by induction on $n$ with a parity count. Call an $(n-1)$ -face of $T$ a door if its vertices carry exactly the colours $0, \ldots, n-1$ . Count pairs (an $n$ -simplex of $T$ , a door in it). A fully coloured simplex has one door, and any other simplex has zero or two. An interior door lies in two simplices, while a boundary door lies in one. All boundary doors lie in the face $\operatorname{conv}\set{v_0, \ldots, v_{n-1}}$ , where their number is odd by induction; so the number of fully coloured simplices is odd.

Example: for $n = 1$ , subdivide a segment from $v_0$ to $v_1$ and colour $v_0$ with $0$ , $v_1$ with $1$ , and the inner points freely. The colour changes an odd number of times along the segment, so an odd number of small segments have both colours.

The boundary condition is needed: if every vertex of $T$ gets the colour $0$ , there is no fully coloured simplex.

Going deeper

For a student

Sperner's lemma is a discrete form of the Brouwer fixed-point theorem: applying it to finer and finer triangulations and passing to a limit gives a fixed point. Its constructive proof by following doors gives algorithms for approximate fixed points and for economic equilibria. It is also used for fair division problems, such as envy-free cake cutting.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Convex hull concept
Simplicial complex concept
Sperner's lemma statement

Tag	`HQG3V5Z6MR`
URI	`m2://HQG3V5Z6MR`
Kind	statement, lemma
Writing	W0 stub
MSC	05E45, 55M20
Status	This copy of the site has no build data. Run `m2 status HQG3V5Z6MR`.
About	Simplicial complex
Uses	Simplicial complex, Convex hull
Same as	Wikidata Q733336 Wikipedia Sperner's lemma
Changed	2 November 2026