クネーザーグラフ
クネーザーグラフは頂点推移的かつ辺推移的である。各頂点は必ず ( n − k k ) {\displaystyle \textstyle {\binom {n-k}{k}}} 個の隣を持つ。しかしながら、一般的にクネーザーグラフは強正則グラフではない。なぜならば、隣接していない頂点同士の複数のペアは、その対応する集合のペアの共通部分の大きさに依存して、共通に持つ近傍の数が異なるからである。
Kneser (1955)が予想したように、クネーザーグラフ KGn,k の彩色数は必ず n − 2k + 2 となる。例えば、ピーターセングラフはどのような特定の彩色に対しても三つの色を必要とする。László Lovász (1978) はこの事実を、位相的組合せ論(英語版)の分野における位相的手法を用いることによって証明した。その後まもなく、Imre Bárány (1978) はボルサック-ウラムの定理(英語版)とデヴィッド・ゲールの補題を用いることによって、簡単な証明を与え、さらに Greene (2002) は簡略化ではあるが依然として位相的な証明を与えることによってモーガン賞(英語版)を得た。また、Matoušek (2004) は純粋な組合せ論的証明(英語版)を与えた。
n ≥ 3k であるなら、クネーザーグラフは常にハミルトン閉路を含む (Chen 2000)。計算機的な研究によれば、n ≤ 27 であるようなすべての連結なクネーザーグラフは、ピーターセングラフを除き、ハミルトンである (Shields 2004)。
n 個の頂点を持つ完全グラフはクネーザーグラフ KGn,1 である。
クネーザーグラフ KG2n − 1,n − 1 は奇グラフ(英語版) On として知られる。奇グラフ O3 = KG5,2 はピーターセングラフと同型である。