Feladat: 5.12.
Határozzuk meg minden
n,k számpárra, hogy hány automorfizmusa van annak a páros gráfnak, amelynek egyik csoportjában
k, másik csoportjában
n pont van? (A
Kn,k
teljes páros gráfnak.)
Hány orbitja van ezeknek a gráfoknak?
Megoldás: 5.12
A
Kn,k
teljes páros gráfnak két orbitja van, ha
k és
n különböző, viszont egy orbitja van, ha
k=n.
Ha
k≠n, akkor a két csoport csak külön-külön permutálható, tehát
k!n! az automorfizmusok száma. Ha
k=n, akkor a két csoport is felcserélhető, tehát
2n
!2
az automorfizmusok száma.