Feladat: 3.22.
Bizonyítsuk be, hogy ha egy gráfban
a) van
C9
, akkor vagy a gráfban, vagy a komplementerében van
C8
is;
b) van
C9
, akkor vagy a gráfban, vagy a komplementerében van
C6
is;
c) valamely ötnél nagyobb
n-re van
Cn
, akkor vagy a gráfban, vagy a komplementerében van
C6
;
d) van
C10
, akkor vagy a gráfban, vagy a komplementerében van
C8
.
Megoldás: 3.22
A pontokat ismét számokkal jelöljük.
a) Legyen a
C9
az
1234567891 kör, a számozást mod 9 tekintjük. Ha valamely
i-re az
i,i+2 él a gráfban van, akkor ez a kör többi pontjával egy
C8
-at zár be. Ha minden ilyen él a komplementerben van, akkor
1357924681 egy
C9
a komplementerben. Ha ennek egyik legrövidebb átlója szintén a komplementerben van, akkor a komplementerben van egy
C8
. Ellenkező esetben minden
i,i+4 él a gráfban van. Ekkor az
159432761 kör egy
C8
a gráfban. (A
2,7 él azonos a
7,11 éllel, a
6,1 él a
6,10 éllel.)
b) Ez következik a)-ból és a
3.21. feladat b) részéből.
c) Teljes indukció
n-re, ugyanúgy megy, mint a
3.20. feladat c) részében.
d) Legyenek a
C10
pontjai sorrendben
1,2,3,4,5,6,7,8,9,10,1, a pontokat mod 10 számozzuk. Ha valamelyik
i-re a gráfban van az
i,i+2 él, akkor ez egy
C9
-et zár be és a) szerint kész vagyunk. Ha pedig az
i,i+3 él van a gráfban, akkor rögtön egy
C8
-at kapunk. Marad az az eset, ha minden
i,i+2 és
i,i+3 él a komplementerben van. Ekkor az
135798641 egy
C8
a komplementerben.