Grafo di Kneser
I grafici di Kneser formano una famiglia infinita di grafici. Il grafo di Kneser con è un Grafo semplice i cui vertici corrispondono ai sottoinsieme di elementi di un insieme di elementi. Due vertici sono collegati se corrispondono a due sottoinsiemi disgiunti.
Il grafo isomorfo al Grafo di Petersen.
Il grado del grafo è quindi mentre la taglia è , si vede facilmente usando il fatto che è un grafo regolare, quindi la somma dei gradi dei vertici è semplice, ed usando l’Handshake Lemma si arriva ad .