,p_{n} be the first n + 1 prime numbers. All vertices of a simplex
S =

[x ,⋅⋅⋅,x ]
0 n

having

{x − x }
k 0

_{k=1}^{n} independent will be labeled with one of these primes. In particular,
the vertex x_{k} will be labeled as p_{k} if the simplex is

[x ,⋅⋅⋅,x ]
0 n

. The value of a simplex will be the product
of its labels. Triangulate this S. Consider a 1 simplex coming from the original simplex

[x ,x ]
k1 k2

, label x_{k1}
as p_{k1} and the other as p_{k2}. Then label all other vertices of this triangulation which occur on

[x ,x ]
k1 k2

either p_{k1} or p_{k2}. Note that by independence of

{x − x }
k r

_{k≠r}, this cannot introduce an inconsistency
because the segment cannot contain any other vertex of S. Then obviously there will be an odd number of
simplices in this triangulation having value p_{k1}p_{k2}, that is a p_{k1} at one end and a p_{k2} at the
other. Suppose that the labeling has been done for all vertices of the triangulation which are on

[x ,...x ]
j1 jk+1

,

{xj1,...,xjk+1} ⊆ {x0,...,xn}

any k simplex for k ≤ n− 1, and there is an odd number of simplices from the triangulation having value
equal to ∏_{i=1}^{k+1}p_{ji} on this simplex. Consider Ŝ≡

[x ,...x ,x ]
j1 jk+1 jk+2

. Then by induction, there is an
odd number of k simplices on the s^{th} face

[ ]
xj1,...,ˆxjs,⋅⋅⋅,xjk+1

having value ∏_{i≠s}p_{ji}. In particular the
face

[ ]
xj1,...,xjk+1,ˆxjk+2

has an odd number of simplices with value ∏_{i≤k+1}p_{ji}. Now no
simplex in any other face of Ŝ can have this value by uniqueness of prime factorization. Lable the
“interior” vertices, those u having all s_{i}> 0 in u = ∑_{i=1}^{k+2}s_{i}x_{ji}, (These have not yet been
labeled.) with any of the p_{j1},

⋅⋅⋅

,p_{jk+2}. Pick a simplex on the face

[ ]
xj1,...,xjk+1,ˆxjk+2

which
has value ∏_{i≤k+1}p_{ji} and cross this simplex into Ŝ. Continue crossing simplices having value
∏_{i≤k+1}p_{ji} which have not been crossed till the process ends. It must end because there are an odd
number of these simplices having value ∏_{i≤k+1}p_{ji}. If the process leads to the outside of Ŝ,
then one can always enter it again because there are an odd number of simplices with value
∏_{i≤k+1}p_{ji} available and you will have used up an even number. When the process ends, the
value of the simplex must be ∏_{i=1}^{k+2}p_{ji} because it will have the additional label p_{jk+2} on a
vertex since if not, there will be another way out of the simplex. This identifies a simplex in the
triangulation with value ∏_{i=1}^{k+2}p_{ji}. Then repeat the process with ∏_{i≤k+1}p_{ji} valued simplices on

[ ]
xj1,...,xjk+1,ˆxjk+2

which have not been crossed. Repeating the process, entering from the outside,
cannot deliver a ∏_{i=1}^{k+2}p_{ji} valued simplex encountered earlier. This is because you cross
faces labeled ∏_{i≤k+1}p_{ji}. If the remaining vertex is labeled p_{ji} where i≠k + 2, then this yields
exactly one other face to cross. There are two, the one with the first vertex p_{ji} and the next
one with the new vertex labeled p_{ji} substituted for the first vertex having this label. Thus
there is either one route in to a simplex or two. Thus, starting at a simplex labeled ∏_{i≤k+1}p_{ji}
one can cross faces having this value till one is led to the ∏_{i≤k+1}p_{ji} valued simplex on the
selected face of Ŝ. In other words, the process is one to one in selecting a ∏_{i≤k+1}p_{ji} vertex from
crossing such a vertex on the selected face of Ŝ. Continue doing this, crossing a ∏_{i≤k+1}p_{ji}
simplex on the face of Ŝ which has not been crossed previously. This identifies an odd number
of simplices having value ∏_{i=1}^{k+2}p_{ji}. These are the ones which are “accessible” from the
outside using this process. If there are any which are not accessible from outside, applying the
same process starting inside one of these, leads to exactly one other inaccessible simplex with
value ∏_{i=1}^{k+2}p_{ji}. Hence these inaccessible simplices occur in pairs and so there are an odd
number of simplices in the triangulation having value ∏_{i=1}^{k+2}p_{ji}. We refer to this procedure of
labeling as Sperner’s lemma. The system of labeling is well defined thanks to the assumption that

{xk − x0}

_{k=1}^{n} is independent which implies that

{xk − xi}

_{k≠i} is also linearly independent.
Thus there can be no ambiguity in the labeling of vertices on any “face” the convex hull of
some of the original vertices of S. The following is a description of the system of labeling the
vertices.

Lemma 18.10.2Let

[x0,⋅⋅⋅,xn]

be an n simplex with

{xk − x0}

_{k=1}^{n}independent, and let thefirst n + 1 primes be p_{0},p_{1},

⋅⋅⋅

,p_{n}. Label x_{k}as p_{k}and consider a triangulation of this simplex.Labeling the vertices of this triangulation which occur on

[xk1,⋅⋅⋅,xks]

with any of p_{k1},

⋅⋅⋅

,p_{ks},beginning with all 1 simplices

[xk1,xk2]

and then 2 simplices and so forth, there are an odd number ofsimplices

[yk1,⋅⋅⋅,yks]

of the triangulation contained in

[xk1,⋅⋅⋅,xks]

which have value p_{k1},

⋅⋅⋅

,p_{ks}.This for s = 1,2,

⋅⋅⋅

,n.

A combinatorial method

We now give a brief discussion of the system of labeling for Sperner’s lemma from the point of view of
counting numbers of faces rather than obtaining them with an algorithm. Let p_{0},

⋅⋅⋅

,p_{n} be the first n + 1
prime numbers. All vertices of a simplex S =

[x0,⋅⋅⋅,xn]

having

{xk − x0}

_{k=1}^{n} independent will
be labeled with one of these primes. In particular, the vertex x_{k} will be labeled as p_{k}. The
value of a simplex will be the product of its labels. Triangulate this S. Consider a 1 simplex
coming from the original simplex

[xk1,xk2]

, label one end as p_{k1} and the other as p_{k2}. Then
label all other vertices of this triangulation which occur on

[xk1,xk2]

either p_{k1} or p_{k2}. The
assumption of linear independence assures that no other vertex of S can be in

[xk1,xk2]

so
there will be no inconsistency in the labeling. Then obviously there will be an odd number of
simplices in this triangulation having value p_{k1}p_{k2}, that is a p_{k1} at one end and a p_{k2} at the
other. Suppose that the labeling has been done for all vertices of the triangulation which are on

[ ]
xj1,...xjk+1

,

{ }
xj1,...xjk+1 ⊆ {x0,...xn}

any k simplex for k ≤ n− 1, and there is an odd number of simplices from the triangulation having value
equal to ∏_{i=1}^{k+1}p_{ji}. Consider Ŝ≡

[ ]
xj1,...xjk+1,xjk+2

. Then by induction, there is an odd number of k
simplices on the s^{th} face

[ ]
xj1,...,ˆxjs,⋅⋅⋅,xjk+1

having value ∏_{i≠s}p_{ji}. In particular the face

[ ]
xj1,...,xjk+1,ˆxjk+2

has an odd number of simplices with
value ∏_{i=1}^{k+1}p_{ji} :=

Pˆ

_{k}. We want to argue that some simplex in the triangulation which is
contained in Ŝ has value

Pˆ

_{k+1} := ∏_{i=1}^{k+2}p_{ji}. Let Q be the number of k + 1 simplices from the
triangulation contained in Ŝ which have two faces with value

ˆP

_{k} (A k + 1 simplex has either 1
or 2

Pˆ

_{k} faces.) and let R be the number of k + 1 simplices from the triangulation contained
in Ŝ which have exactly one

Pˆ

_{k} face. These are the ones we want because they have value

Pˆ

_{k+1}. Thus the number of faces having value

ˆP

_{k} which is described here is 2Q + R. All interior

Pˆ

_{k} faces being counted twice by this number. Now we count the total number of

ˆP

_{k} faces
another way. There are P of them on the face

[xj,...,xj ,ˆxj ]
1 k+1 k+2

and by induction, P is
odd. Then there are O of them which are not on this face. These faces got counted twice.
Therefore,

2Q + R = P + 2O

and so, since P is odd, so is R. Thus there is an odd number of

ˆP

_{k+1} simplices in Ŝ.

We refer to this procedure of labeling as Sperner’s lemma. The system of labeling is well defined thanks
to the assumption that

{x − x }
k 0

_{k=1}^{n} is independent which implies that

{x − x }
k i

_{k≠i} is also linearly
independent. Thus there can be no ambiguity in the labeling of vertices on any “face”, the
convex hull of some of the original vertices of S. Sperner’s lemma is now a consequence of this
discussion.