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.
Segítség, útmutatás: 6.1
Válasszunk ki egy legnagyobb fokú pontot és egy másik, vele össze nem kötött pontot próbáljunk ,,hasonlóvá tenni" hozzá!
Megoldás: 6.1