Megoldás: 4.22
1. megoldás. Egy ötelemű halmaznak tíz kételemű részhalmaza van, tehát a
KG(5,2) Kneser-gráfnak tíz pontja van. Egy kételemű részhalmaz pontosan három másiktól diszjunkt, tehát a Kneser-gráf minden pontjának fokszáma 3. Végül az is világos, hogy ha két kételemű halmaznak van közös pontja, akkor van olyan kételemű halmaz (pontosan egy), amely mindkettőtől diszjunkt. Tehát a Kneser-gráf bármely két, éllel össze nem kötött pontjának van közös szomszédja, tehát a
KG(5,2) Kneser-gráf 10-pontú, 3-reguláris, 2-átmérőjű gráf.
A
K.II.8.13. feladatból tudjuk, hogy egyetlen ilyen gráf van, ami a
K.II.8.13. feladat szerint a Petersen-gráf. Tehát a
KG(5,2) gráf a Petersen-gráf.
2. megoldás. Közvetlenül is megtalálhatjuk a megfeleltetést a Petersen-gráf és a
KG(5,2) Kneser-gráf között. Válasszuk az ötelemű alaphalmaznak az
{1,2,3,4,5} halmazt. A ,,külső kerék" pontjai lehetnek (ilyen sorrendben) az
{1,2},
{3,4},
{5,1},
{2,3},
{4,5}, a ,,belső kerék" pontjai az
{3,5},
{5,2},
{2,4},
{4,1},
{1,3}, itt a sorrendet a ,,küllők" szerint adtuk meg, tehát itt minden második van éllel összekötve. Lásd . ábrát.