Kneser graphs
Let be positive integers with . The Kneser graph has as its vertex set the -element subsets of . Two vertices are adjacent if and only if they correspond to disjoint subsets.
The graph is the complete graph on vertices. Another well-known Kneser graph is , better known as the Petersen graph
, which is shown in figure 1. The Petersen graph is often a counterexample to graph-theoretical conjectures.