Let $k,n$ be positive integers with $k\leq n$. The Kneser graph $K_{{n:k}}$ has as its vertex set the $n\choose k$ $k$-element subsets of $\{1,2,\dots,n\}$. Two vertices are adjacent if and only if they correspond to disjoint subsets.

The graph $K_{{n:1}}$ is the complete graph on $n$ vertices. Another well-known Kneser graph is $K_{{5:2}}$, better known as the Petersen graph, which is shown in figure 1. The Petersen graph is often a counterexample to graph-theoretical conjectures.