A combinatorial conjecture formulated by Kneser (1955). It states that whenever the -subsets
of a -set
are divided into
classes, then two disjoint subsets end up in the same class.

Lovász (1978) gave a proof based on graph theory. In particular, he showed that the Kneser graph, whose vertices represent the
-subsets,
and where each edge connects two disjoint subsets, is not -colorable. More precisely, his results says that the chromatic number is equal to , and this implies that Kneser's conjecture is always false
if the number of classes is increased to .

Bárány, I. "A Short Proof of Kneser's Conjecture." J. Comb. Th. A25, 325-326, 1978.Godsil,
C. and Royle, G. Algebraic
Graph Theory. New York: Springer-Verlag, p. 160, 2001.Kneser,
M. "Aufgabe 300." Jahresber. Deutsch. Math.-Verein58, 1955.Lovász,
L. "Kneser's Conjecture, Chromatic Numbers and Homotopy." J. Comb. Th.
A25, 319-324, 1978.