Feladat: 3.19.
a) Bizonyítsuk be, hogy 5→( C4 , C4 ) nem igaz. b) Mutassuk meg, hogy 3n-2→( C2n , C2n ) nem igaz, tehát van olyan 3n-2 pontú gráf, amelyben nincs Cn és ez a komplementerére is igaz. c) Mutassuk meg, hogy 2n-2→( Cn , Cn ) nem igaz, ha n páratlan. Vagyis páratlan n-re van olyan 2n-2 pontú gráf, amelyben nincs Cn és a komplementerében sincs Cn .
Megjegyzés. Igaz viszont, hogy 3n-1→( C2n , C2n ), ha n≥3; valamint páratlan n-re 2n-1→( Cn , Cn ), ha n≥5. Ennek bizonyítása azonban sokkal bonyolultabb. Az alábbiakban (3.20.-3.28. feladat) néhány olyan feladatot mutatunk, amelyek legalább a bizonyítás gondolatvilágába bevezetnek.
 

Megoldás: 3.19
a) Ha G egy ötpontú kör ( C5 ), akkor a komplementere is az és egyikben sincs C4 .

b) Álljon a gráf egy 2n-1 pontú teljes gráfból és egy n-1 pontú teljes gráfból. Ebben a gráfban nyilván nincs C2n , hiszen mindkét komponensének kevesebb pontja van 2n-nél. Viszont a komplementer egy páros gráf, amelynek egyik osztályában csak n-1 pont van, így a leghosszabb kör is csak 2n-2 pontból áll.

c) Álljon a gráf két n-1 pontú pontdiszjunkt teljes gráfból. Ebben a gráfban nyilván nincs n pontú kör. A komplementere viszont páros gráf, abban tehát egyáltalán nincs páratlan kör, így Cn sem.