Feladat: 3.21.
a) Bizonyítsuk be, hogy ha egy gráfban van C7 , akkor vagy a gráfban, vagy a komplementerében van C6 is. b) Bizonyítsuk be, hogy ha egy gráfban van C8 , akkor vagy a gráfban, vagy a komplementerében van C6 is.
 

Megoldás: 3.21
A pontokat ismét számokkal jelöljük.

a) Legyen a C7 az 12345671 kör, a számozást mod 7 tekintjük (tehát például a 9-es pont azonos a 2-essel). Ha valamely i-re a gráfban van az i és i+2-t összekötő él, akkor ez egy C6 -ot zár be és kész vagyunk. Ha minden i-re a komplementerben van az él, akkor az 13572461 egy C7 -et alkot a komplementerben. Ha valamely i-re az i-t és i+4-et összekötő él a komplementerben van, akkor a komplementerben találtunk egy C7 -et. Ha viszont minden i,i+4 él a gráfban van, tehát például az 15 és a 37 él is a gráfban van, akkor az 1567321 egy C6 a gráfban.

b) Legyen a C8 az 123456781 kör, a számozást mod 8 tekintük. Ha valamely i,i+2 él a gráfban van, akkor van C7 a gráfban, s ekkor a) szerint kész vagyunk. Ha valamely i,i+3 él a gráfban van, akkor ez egy C6 -ot zár be és ismét kész vagyunk. Marad az az eset, ha minden ilyen él a komplementerben van. Ekkor viszont az 1368241 egy C6 a komplementerben.