Feladat: 12.18.
A Turán-tétel azonban általánosabb, mint a
12.17. feladatban szereplő tétel, amely csak háromszögekről szól. Az általános Turán-tétel minden
k-ra megadja, hogy egy
n pontú gráfban hány él kell ahhoz, hogy biztosan legyen benne teljes
k-as gráf. Bizonyítsuk be az alábbi
k=4 esetet:
Turán-tétel.
Ha egy
n pontú gráfban van legalább
n2
/3 él, akkor van benne négypontú teljes gráf.
Megoldás: 12.18
Azt nézzük meg, hogy ha egy
n pontú gráfban nincs teljes négyes, legfeljebb hány éle lehet.
Vegyünk ismét egy legnagyobb fokú pontot, legyen ez az
x pont, és legyen
d a fokszáma. A vele össze nem kötött
n-d-1 darab pont mindegyike legfeljebb
d-ed fokú. Ez eddig legfeljebb
d(n-d) él.
Másrészt az
x-szel összekötött pontok
V halmaza által alkotott
d pontú gráfban nem lehet három pontú teljes gráf (ha volna,
x-szel egy négy pontú teljes gráfot alkotnának). Tehát
V pontjai között legfeljebb
d2
/4 él futhat. Ez azt jelenti, hogy a gráfban összesen legfeljebb
él. A számtani és mértani közép közötti egyenlőtlenség szerint
3d(4n-3d)≤(3d+4n-3d
)2
/4=4
n2
.
Ezt összehasonlítva előző eredményünkkel azt kapjuk, hogy a gráfnak legfeljebb
n2
/3 éle lehet.
A most kapott eredmény csak hárommal osztható
n-ekre pontos. Ha
n=3k, akkor egy olyan gráf a példa, amelyben a pontokat három, egyenként
k pontú osztályba soroltuk és a különböző osztályba tartozó pontokat kötjük össze. A bizonyításból az is kiolvasható, hogy ez az egyetlen példa
n pontú,
n2
/3 élű gráfra, amelyben nincs négypontú teljes gráf.
Ha
n=3k+1, akkor az egyik osztályba
k+1 pontot kell tennünk, hogy a maximális élszámú gráfot megkapjuk, ha pedig
n=3k+2, akkor két osztályba kell
k+1 pontot tennünk. A bizonyításból ez is ,,kigyötörhető" lenne, de másutt (l. a
GR.II.2.12. feladatot) adunk rá olyan bizonyítást, amelyből e két eset kevesebb számolással is kijön.
Megjegyzés. Az állítás úgy is fogalmazható, hogy a legtöbb él úgy helyezhető el egy teljes négyest nem tartalmazó
n pontú gráfban, ha a pontokat a lehető legegyenletesebben három osztályba soroljuk és a különböző osztályokba tartozó pontokat összekötjük.