Feladat: 5.8.
Legyen
P és
Q egy gráf két pontja.
a) Bizonyítsuk be, hogy pontosan annyi automorfizmus viszi a
P pontot
Q-ba, mint a
Q pontot
P-be.
b) Bizonyítsuk be az
5.7. feladat megoldásában használt állítást:
Ha a
P pontot a helyén hagyó automorfizmusok száma
k, akkor ugyanennyi automorfizmus viszi át a gráfot a
P-vel egy orbitban levő
Q pontba.
Megoldás: 5.8
a) Ha egy
s automorfizmus a
P pontot a
Q pontba viszi, akkor az inverze is automorfizmus, és az a
Q pontot viszi
P-be. Ugyanígy ha a
t automorfizmus a
Q pontot a
P pontba viszi, akkor az inverze a
P pontot viszi a
Q pontba. Mivel különböző automorfizmusok inverze is különböző, ebből következik, hogy a
P-t
Q-ba vivő automorfizmusok száma megegyezik a
Q-t
P-be vivő automorfizmusok számával.
b) Van egy olyan
s automorfizmus, amely a
P pontot a
Q pontba viszi. Ha minden, a
P pontot a helyén hagyó
t automorfizmust megszorozzuk ezzel az
s automorfizmussal, akkor az
st automorfizmus (előbb hajtjuk végre
t-t, aztán
s-et) a
P pontot a
Q-ba vivő automorfizmust kapunk. Ha
t és
t' különböző, akkor az
st és az
st' automorfizmusok is különbözők. (Ha
st=st' volna, akkor
s inverzével,
s-1
-gyel mindkettőt megszorozva azt kapnánk, hogy
t=t'.)
Ezzel beláttuk, hogy a
P-t
Q-ba vivő automorfizmusok száma legalább annyi, mint a
P-t helyben hagyóké. Legyen most
t egy olyan automorfizmus, ami
P-t
Q-ba viszi. Ha ez után rendre alkalmazzuk a
Q-t
P-be vivő automorfizmusokat, akkor rendre különböző,
P-t a helyén hagyó automorfizmusokat kapunk. Tehát legalább annyi
P-t a helyén hagyó automorfizmus van, mint ahány
Q-t
P-be vivő automorfizmus.
Jelöljük
n(P,Q)-val a
P-t
Q-ba vivő automorfizmusok számát. Azt kaptuk, hogy
n(P,Q)≥n(P,P)≥n(Q,P).
Az a) feladat szerint
n(P,Q)=n(Q,P), s ebből már következik, hogy
n(P,Q)=n(P,P), ami szavakban elmondva éppen a feladat állítása.