Feladat: 2.23.
a) Mutassuk meg, hogy minden 12 pontú, 4-reguláris egyszerű gráf tartalmaz
C4
-et.
b) Tudjuk, hogy van egy
n pontú,
k reguláris egyszerű gráf, amelyben nincs
C4
és legyen
H egy
n elemű halmaz. Bizonyítsuk be, hogy megadható a
H halmaznak
n darab
k elemű részhalmaza úgy, hogy bármely kettőnek legfeljebb egy közös eleme van.
Megoldás: 2.23
a) Ha volna 12 pontú, 4-reguláris gráf, amelyben nincs
C4
, akkor ismét alkalmazható, amit a
2.22. feladat b) részében csináltunk: minden ponthoz hozzárendeljük a ,,szomszédsági" halmazát. Így 12 darab olyan négyelemű halmazt kapnánk, amelyek közül semelyik kettőnek nincs egynél több közös pontja. De egy-egy négyelemű halmaz 6 elempárt fed le, tehát összesen 72 elempárt számolhatunk össze e 12 halmazban. A 12 pontú halmazból azonban csak 66 különböző elempárt választhatunk ki. Tehát van olyan elempár, amit a négyelemű pontok többszörösen lefednek. Ha
x-et és
y-t egyaránt lefedi az
a-hoz és
b-hez tartozó szomszédsági halmaz, akkor
axby négypontú kör a gráfban.
b) bizonyítása pontosan ugyanúgy megy, mint a
2.22. feladat b)-é.