Kneser

s conjecture, first proved by Lovász in 1978,
states that the graph with all
k-element subsets of {1, 2, . . . ,
n} as vertices and with edges
connecting disjoint sets has chromatic number
n–2
k+2. We derive this result from
Tucker

s combinatorial lemma on labeling the vertices of special
triangulations of the octahedral ball. By specializing a proof
of Tucker

s lemma, we obtain self-contained purely combinatorial
proof of Kneser

s conjecture.
Mathematics Subject
Classification (2000): 05C15 - 05A05 - 55M35
* Research supported by Charles University grants
No. 158/99 and 159/99 and by ETH Zürich.