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.
Megoldás: 6.1
Feltesszük, hogy a gráfban nincs háromszög és megnézzük, maximálisan hány éle lehet. A megoldást hasonlóan kezdjük, mint a
K.II.12.17. feladat megoldásában (az egész megoldást érdemes összevetni az ottani megoldással!!): kiválasztjuk a gráf egy maximális fokú
x pontját. E maximális fokszámot most is
d-vel jelöljük és most is
S-sel jelöljük
x szomszédait. A gráfban nincs háromszög, tehát
S-ben nem fut él. Jelöljük
T-vel a többi - tehát
x-szel össze nem kötött - pont halmazát, és legyen ennek egy tetszőleges pontja
y. Töröljük ki az
y-ból induló éleket és húzzuk be helyette az
y-t
S pontjaival összekötő
d darab élet. A
d maximalitása miatt legalább annyi élt húztunk be, ahányat elhagytunk, tehát a gráf élszáma nem csökkent. Másrészt könnyen látható, hogy nem keletkezett háromszög, hiszen új háromszög csak úgy keletkezhetne, hogy annak egyik pontja
y, de az
y-nal összekötött pontok között nem fut él.
Ezt az eljárást megismételhetjük
S minden pontjára, s ekkor eljutunk egy olyan páros gráfhoz, amelynek két osztálya
S és
T∪{x}, s köztük minden él be van húzva, azaz teljes páros gráfról van szó. Eközben nem csökkent a gráf élszáma.
Ismert, hogy egy
n pontú teljes páros gráfnak akkor van a legtöbb éle, ha páros
n esetén a két osztályban azonos számú pont van, páratlan
n esetén akkor, ha a két osztály pontszáma eggyel tér el. Első esetben
n2
/4 éle van a gráfnak, a második esetben
(
n2
-1)/4 éle van. Az eredeti gráfnak is legfeljebb ennyi éle van tehát.
A bizonyításból most is az adódik, hogy egyenlőség pontosan akkor van, ha olyan teljes páros gráfról van szó, amelynek két osztályában vagy megegyezik a pontok száma (az
n=2k páros eset), vagy eggyel különbözik (az
n=2k+1 páratlan eset).
Megjegyzés. Érdemes végiggondolni, hogy ez az úgynevezett ,,szimmetrizálási eljárás" lényegében ugyanazt ,,csinálja", mint a ,,Vegyük a legnagyobbat" fejezetben adott megoldás (l. a
K.II.12.17. feladat megoldását). Ez kicsit ,,szemléletesebben" mutatja azt, ami ott is történik.