Turán-tétel
A Turán-tétel vagy Turán-féle gráftétel meghatározza, hogy legfeljebb hány éle lehet egy (teljes véges) gráfnak, amely nem tartalmaz adott nagyságú teljes gráfot. Turán Pál 1941-ben publikálta tételét, ami a gráfelmélet egy jelentős fejezetét, az extremális gráfelméletet indította el.[1]
A tétel
Egyszerűbb formájában a tétel a következőt mondja: ha egy n szögpontú gráfban nincs (teljes k+1-es), akkor éleinek száma legfeljebb
A tétel teljes formája szerint, ha , ahol és egy n pontú gráfban nincs , akkor az élek e számára
teljesül. Ez minden n-re pontos, egyenlőség egyetlen gráfra, a T(n,k) Turán-gráfra teljesül: ez k közös elem nélküli halmazból áll, ahol , , két pontot pontosan akkor kötünk össze, ha különböző osztályokban vannak.
A háromszög nélküli eset
Ebben a speciális esetben (amit Mantel már 1907-ben igazolt) azt kell belátnunk, hogy ha egy n szögpontú gráfban nincs háromszög, akkor az élek e számára teljesül.
Első bizonyítás
Legyenek a csúcsok . Tegyük fel, hogy a és a csúcsok össze vannak kötve. A további pont egyike sem lehet mindkettővel összekötve. Ezen pontból és van összekötve -vel, illetve -vel (ahol a v pont foka). Mivel egyik sem lehet mindkettővel összekötve, kapjuk, hogy
azaz
Ezt minden összekötött pontpárra összeadva a jobb oldal en lesz, a bal oldalban pedig minden tag annyiszor szerepel, ahány élben van, azaz -szor. Tehát
adódik.
A számtani és négyzetes közép közötti egyenlőtlenséget felhasználva
Mivel , a fenti egyenlőtlenséget így alakíthatjuk:
ami átrendezve éppen a bizonyítandó állítás.
Második bizonyítás
Legyen a legnagyobb független (élnélküli) ponthalmaz elemszáma k és legyen A egy k elemű független halmaz. Jelöljük B-vel A komplementerét. Mivel a gráfban nincs háromszög, minden pont szomszédainak halmaza független, tehát legfeljebb k elemű. Továbbá minden élnek egyik, esetleg mindkét végpontja B-beli (mert A független), így az élek e számára a következőt kapjuk:
az utolsó lépésben felhasználva a számtani és mértani közép közötti egyenlőtlenséget.
Az általános eset bizonyítása
A tételt q-ra indukcióval igazoljuk. Ha q=0, akkor tehát a gráfnak r<k csúcsa van, semmiképpen sem lehet benne teljes (k+1)-szög, az élek maximális száma így
amint azt kiszorzással láthatjuk.
Tegyük fel, hogy q>0 és adott egy n szögpontú és maximális élszámú -et nem tartalmazó gráf. Ebben mindenképpen van teljes k-as, különben egy élt még hozzá tudnánk adni. Legyen A egy k elemű teljes ponthalmaz, B pedig a maradék pontok halmaza. Nyilván B elemszáma n-k. Jelölje a,b,c rendre az A-ban, B-ben, illetve A és B között futó élek számát. Nyilván . Mivel A teljes gráf,
Az indukció miatt azt is tudjuk, hogy
Egyetlen B-beli pont sem lehet összekötve minden A-belivel, hiszen ekkor lenne egy teljes (k+1)-es. Azaz minden B-beli pontból legfeljebb k-1 él megy A-ba, így minden pontra összeszámolva adódik .
Összeadva adódik
ami, mint kiszorzással látható, azonos a következővel:
Be kell még látnunk, hogy egyenlőség csak a Turán-gráf esetén teljesül. Ha egyenlőség van, akkor b és c esetén is egyenlőségnek kell teljesülnie. Azaz minden B-beli csúcs k-1 A-beli csúccsal van összekötve és (az indukció miatt) B a T(n-k,k) Turán-gráf. B felbomlik a majdnem egyenlő nagyságú halmazokra és pontosan a különböző halmazokban levő csúcsok vannak összekötve. Két különböző -ben levő csúcs nem lehet ugyanazzal a k-1 A-beli csúccsal összekötve, mert ekkor teljes k+1-est kapnánk. Mivel A-nak pontosan k darab k-1 elemű részhalmaza van, csak az lehet, ha minden -beli csúcs ugyanabba az A-beli csúcsba nincs bekötve, és ez különböző i-re különböző, ezért A elemeit felsorolhatjuk -ként, hogy elemei pontosan -be nincsenek bekötve. De ezzel azt kapjuk, hogy gráfunk a Turán-gráf az osztályokkal.
Források
- ↑ Lovász László: Kombinatorikai problémák és feladatok. 34-38. old. Typotex Kiadó, 2008. ISBN 978-963-9664-93-7
Matematikaportál • összefoglaló, színes tartalomajánló lap