Feladat: 4.26.
G és
G' azonos pontszámú
d-reguláris gráfok. Tudjuk, hogy
G-nek van olyan
x pontja és
G'-nek van olyan
x' pontja, amelyre
G-x és
G-x' izomorfak. Következik-e ebből, hogy
G és
G' is izomorf?
Megoldás: 4.26
Igen. A feltételből következik ugyanis, hogy
a)
x és
x' fokszáma is
d,
b)
G-x-ben
x szomszédainak fokszáma
d-1, minden más pont foka
d,
c)
G-x'-ben
x' szomszédainak fokszáma
d-1, minden más pont foka
d.
Másrészt
G-x és
G-x' izomorf, s az az egy-egyértelmű
t leképezés, amely ezt bizonyítja,
x szomszédai és
x' szomszédai között egy-egy értelmű megfeleltetés (mert csak ezek a pontok
d-1-ed fokúak). Ha tehát a
t izomorfiát kiterjesztük úgy, hogy
x-nek
x'-t feleltesse meg,
G egy izomorfiájához jutunk.