En teoría de grafos, el grafo de Kneser K(n, k) (alternativamente KGn,k) es el grafo cuyos vértices corresponden a los subconjuntos de k elementos de un conjunto de n elementos, y donde dos vértices son adyacentes si y solo si los dos correspondientes conjuntos son disjuntos.

El grafo de Kneser O4= K(7, 3), visualizado a la derecha.

Esta conjetura se ha demostrado de varias maneras.

El grafo de Kneser generalizado K(n, k, s) tiene el mismo conjunto de vértices que el grafo de Kneser K(n, k), pero conecta dos vértices siempre que correspondan a conjuntos que se cruzan en s o menos elementos (Denley, 1997).

Dos vértices están conectados por una arista siempre que un conjunto es un subconjunto del otro.

Al igual que el grafo de Kneser, es vértice transitivo con grado