Megoldás: 5.29
Igen. A bizonyítás ismét úgy történhet, mint az
5.22. feladatban: annak segítségével, hogy a Petersen-gráf azonos a
KG(5,2) Kneser-gráffal. A különbség az, hogy most az
{1,2,3,4,5} halmaz két nem-diszjunkt, kételemű részhalmazát kell az alaphalmaz egy permutációjával két másik nem-diszjunkt, kételemű részhalmazba átvinni. Ilyen permutáció is van, s ez ugyanúgy terjeszthető ki a Petersen-gráf csúcsainak egy automorfizmusává, mint az
5.22. feladatban. Tehát a Petersen-gráf bármely két ,,nem-éle" (a végpontok megadott sorrendjében) is automorfizmussal egymásba vihető. Tehát a Petersen-gráf komplementere is éltranzitív.