Kneser graph

Definition

Suppose $n$ and $k$ are positive integers. The Kneser graph $K G_{n, k}$ is an undirected graph defined as follows. Fix a set of size $n$ (we usually take the set as ${1, 2, \dots, n}$ for convenience). Then:

The vertex set of $K G_{n, k}$ is the collection of $k$ -element subsets of the fixed set of size $n$ .
The edge set of $K G_{n, k}$ is defined as follows: two vertices of $K G_{n, k}$ are adjacent if and only if they are disjoint when viewed as subsets of the $n$ -element set.

Particular cases

Classes of cases

Condition on $n$ and $k$	Conclusion
$k > n$	The vertex set is empty, so the graph is a graph on no vertices
$k = n$	one-point graph
$n / 2 < k < n$	The vertex set is non-empty, but the edge set is empty, so the graph is an empty graph
$k = n / 2$	In this case, the graph is a matching graph: it is a disjoint union of 2-cliques, with one 2-clique for each partition of the $n$ -set into two disjoint pieces of equal size.
$1 < k < n / 2$	This is the interesting case. In this case, the graph is connected and non-empty, but is not a complete graph.
$k = 1$	complete graph $K_{n}$
$k = 0$	one-point graph

First few nontrivial cases

As indicated above, the interesting cases are where $1 < k < n / 2$ . We list the first few of these:

$n$	$k$	Kneser graph $K G_{n, k}$
5	2	Petersen graph
6	2	Fill this in later