Feladat: 10.17.
a) Egy ötpontú gráfban legfeljebb hány él lehet, ha nincs benne ötpontú kör?
b) Egy hatpontú gráfban legfeljebb hány él lehet, ha nincs benne hatpontú kör?
Megjegyzés. Az általános kérdést tárgyalja a következő
10.18. feladat.
Megoldás: 10.17
a) Egy négypontú teljes gráf és egyik pontjából kiinduló egyetlen él egy olyan hétélű gráf, amelyben nincs ötpontú kör. Ha viszont nyolc él van, akkor a komplementerben csak két él van, ez csak kétféleképp lehetséges és mindkét esetben találunk ötszöget a gráfban.
b) Egy ötpontú teljes gráf és egyik pontjából kiinduló egyetlen él egy olyan 11 élű gráf, amelyben nincs hatpontú kör. Ha viszont 12 él van, akkor a komplementerben csak három él van, ez csak ötféleképp lehetséges és minden eseteben esetben találunk hatszöget a gráfban.