,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} if the simplex is

[x0,⋅⋅⋅,xn ]

. 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}. Note that by independence of

{xk − xr}

_{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

[ ]
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} 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 4.2.1Let

[x0,⋅⋅⋅,xn]

be an n simplex with

{xk − x0}

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

⋅⋅⋅

,p_{n}. Label x_{k}as p_{k}and consider a triangulationof 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 simplicesand so forth, there are an odd number of simplices

[yk1,⋅⋅⋅,yks]

of the triangulationcontained 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 Ŝ≡

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

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

[x ,...,ˆx ,⋅⋅⋅,x ]
j1 js jk+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

[ ]
xj1,...,xjk+1,ˆxjk+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

{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. Sperner’s lemma
is now a consequence of this discussion.