Feladat: 5.11.
Hány automorfizmusa van
a) a három-ház-három-kút gráfnak;
b) annak a teljes páros gráfnak, amelynek egyik csoportjában három, másik csoportjában öt pont van?
Határozzuk meg a gráfok orbitjait.
Megoldás: 5.11
Az a) gráfnak egyetlen orbitja van. A b) gráfnak két orbitja van, a két csoport.
a) A három-ház-három-kút gráfnál először eldöntjük, hogy a két csoportot felcseréljük-e, vagy megtartjuk. Ez egy kettes szorzó. Utána külön-külön bárhogyan permutálhatjuk a két csoport pontjait, ez egy-egy hatos szorzót jelent, a gráfnak tehát 72 automorfizmusa van.
b) Itt a két csoport csak külön-külön permutálható (két orbit van), ezért
6·120=720 automorfizmust kapunk.