Feladat: 4.30.
Döntsük el általában, hogy n milyen értékeire van olgyan n pontú egyszerű gráf, amely izomorf a komplementerével!
 

Megoldás: 4.30
Ha valamely n-re van ilyen gráf, akkor a gráfnak és a komplementerének azonos számú éle kell, hogy legyen. Másrészt a gráfnak és komplementerének együtt n(n-1)/2 éle van. Ha tehát e szám nem páros, akkor nincs ilyen gráf. Vagyis n=4k+2 és n=4k+3 alakú számokra biztosan nincs ilyen gráf.

Másrészt az n=4k esetben az n=8 esethez egészen hasonlóan kapunk megfelelő gráfot (lásd a 4.29. feladatot), csak kettő helyett k darab xi , yi , zi , ui pontot kell felvenni, majd behúzni az xy, yz, uz éleket, továbbá az xi xj és az ui uj éleket ( i≠j). Az izomorfia most is ugyanúgy írható le, mint az n=8 esetben. Innen már n=4k+1 pontra ugyanúgy járhatunk el, mint az n=9 esetben (lásd ugyancsak a 4.29. feladatot): a plusz egy pontot az x és az u pontokkal kötjük össze.