Feladat: 3.5.
a) Bizonyítsuk be, hogy ha egy tízpontú teljes gráfban nincs háromszög, akkor a komplementerében van négypontú teljes gráf. Vagyis 10→(3,4). b) Igaz-e ez kilencpontú gráfra is? c) Mi a helyzet nyolcpontú gráf esetén? (Arany Dániel-verseny 1994)
 

Megoldás: 3.5
a) Vegyünk egy x pontot a gráfból. Nézzük, hány szomszédja lehet. Tudjuk, hogy a szomszédai között nem futhat él. Ha van legalább négy szomszédja, akkor ezek a komplementerben egy teljes négyest alkotnak. Ha viszont legfeljebb három szomszédja van, akkor van hat olyan pont, amellyel nincsen összekötve. Nézzük az ezek által feszített részgráfot. Itt a 3.1. feladat szerint vagy van háromszög, vagy a komplementerben van háromszög. Az előbbi esetet kizártuk, tehát a komplementerben van háromszög. Ennek pontjai x-szel együtt egy négypontú teljes gráfot alkotnak. b) Az a) részben azt kaptuk, hogy ha a gráfban nincs háromszög, és egy pontnak legalább négy szomszédja van, vagy legalább hat ponttal a komplementerben van összekötve, akkor van a komplementerben teljes négyes. Egyetlen eset marad: ha minden pont foka három (és a komplementerben öt). De kilencpontú gráfnál ez nem fordulhat elő, hiszen akkor a fokszámösszeg páratlan volna. Beláttuk tehát, hogy 9→(3,4). A c) részre a 3.7. feladatban fogunk válaszolni. Az világos, hogy ha van ellenpélda, ott minden pont foka legfeljebb három.