Feladat: 4.27.
[4], 14. old. Mely G páros gráfok izomorfak a komplementerükkel?
 

Megoldás: 4.27
Ha G páros gráf, akkor két osztályba sorolhatók a pontjai úgy, hogy azonos osztálybeliek között nem fut él. Ha valamelyik osztályban legalább három pont volna, akkor a komplementerében volna háromszög, tehát a komplementer nem volna páros gráf. Így G mindkét osztályában legfeljebb két-két pont lehet. Az egy pontból álló gráf megfelel. Két és három pontú gráf esetében a teljes gráf élszáma 1, illetve 3, tehát páratlan, így a gráf és a komplementere nem tartalmazhat ugyanannyi élt. Ha G négypontú, akkor a gráf is, komplementere is három élből áll, s ez csak egy 3 élű út, egy háromszög vagy egy háromágú csillag lehet. Utóbbi kettő egymás komplementere, így nem izomorf a komplementerével.

Tehát két ilyen G páros gráf van: az egyetlen pontból álló gráf és a háromélű útból álló gráf.