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 
.
An alternate proof was given by Bárány (1978).
