Feladat: 6.1. Bizonyítsuk be a
Turán-tételt: Ha egy
n pontú egyszerű gráfnak több mint
n2
/4 éle van, akkor van benne háromszög. Másrészt minden
n-re van (izomorfiától eltekintve pontosan egy) olyan
⌊
n2
/4⌋ élű gráf, amelyben nincs háromszög.
Megjegyzés. Erre a tételre több bizonyítást is adunk, lásd még a
2.10. feladat megoldását és a
K.II.12.17. feladat megoldását.
Feladat: 6.2. Készítsünk egy 2000 darab valós számból álló
H halmazt, amelynek egyik eleme sem nulla. Jelöljük
k-val a
H-ből kiválasztható olyan négyelemű részhalmazok számát, amelyekben a négy elem szorzata negatív. A
H elemei közül hányat kell negatívnak választanunk ahhoz, hogy
k értéke a lehető legnagyobb legyen?