Feladat: 4.29.
Azt vizsgáljuk, hogy milyen n-ekre van olyan n pontú egyszerű gráf, amely izomorf saját komplementerével. a) Döntsük el a kérdést az n=1,2,3,4,5,6,7 esetekben! b) Döntsük el a kérdést n=8,9 esetben!
 

Megoldás: 4.29
a) n=1-re az egypontú gráf üres, tehát izomorf a komplementerével.

n=2-re vagy a gráf vagy a komplementere üres, a másik nem, tehát nincs ilyen gráf.

n=3 esetén a teljes gráfnak három éle van, így nem tudjuk őket két egyforma osztályba sorolni, márpedig egy gráf és a komplementere azonos élszámú, ha izomorf.

n=4 esetén a három hosszú út izomorf a komplementerével.

n=5 esetén az ötpontú kör izomorf a komplementerével.

n=6 esetén a teljes gráfnak 15 éle van, ami páratlan, tehát ismét nem lehet ilyen gráf.

n=7 esetén a teljes gráfnak 21 éle van, ami ismét páratlan.

Az első hét szám közül csak n=1,4,5-re van a komplementerével izomorf gráf.

b) n=8 és n=9 esetében viszont van ilyen gráf. n=8-ra legyen a gráf nyolc pontja x1 , x2 , y1 , y2 , z1 , z2 , u1 , u2 . Húzzuk be a gráfba az xi yj , yi zj , zi uj éleket ( i,j=1,2). Ez eddig 12 él. Ha behúzzuk még az x1 x2 és az u1 u2 éleket, akkor egy olyan gráfot kapunk, amely izomorf a komplementerével. Az izomorfiát könnyű megadni: az xi pontnak az yi pont feleljen meg, az yi pontnak az ui , a zi -nek a xi és az ui -nek az zi .

n=9 esetben ebből már könnyű megfelelő gráfot kapni: a kilencedik pontot az x és az u pontokkal kötjük össze.