Feladat: 5.35.
* Az
5.15. feladatban láttuk, hogy a Petersen-gráfnak 120 automorfizmusa van. A
4.22. feladat szerint a Petersen-gráf a
KG(5,2) gráf, láttuk továbbá, hogy a Petersen-gráf automorfizmusai megegyeznek az ötelemű alaphalmaz 120 permutációjából kapható 120 automorfizmussal.
Igaz-e általában is, hogy a
KG(n,k) Kneser-gráfnak pontosan
n! automorfizmusa van?
Megoldás: 5.35
Nem igaz. Az nyilvánvalóan igaz, hogy a
KG(n,k) Kneser-gráfnak van legalább
n! automorfizmusa, amelyet az alaphalmaz permutációiból nyerhetünk, de korántsem biztos, hogy csakis ezek az automorfizmusai vannak. Például a
KG(4,2) gráf az oktaéder komplementere, tehát 48 automorfizmusa van (lásd a
4.21. és az
5.10. feladatokat), ami kétszerese a
4!-nak.