# Kneser graphs

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.

Title Kneser graphs KneserGraphs 2013-03-22 14:16:49 2013-03-22 14:16:49 justice (4961) justice (4961) 5 justice (4961) Definition msc 05C99 Petersen graph