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.

A tétel

Egyszerűbb formájában a tétel a következőt mondja: ha egy n szögpontú gráfban nincs $K_{k+1}$ (teljes k+1-es), akkor éleinek száma legfeljebb

${\frac {k-1}{2k}}n^{2}.$

A tétel teljes formája szerint, ha $n=kq+r$, ahol $0\leq r<k$ és egy n pontú gráfban nincs $K_{k+1}$, akkor az élek e számára

$e\leq {\frac {k-1}{2k}}n^{2}-{\frac {r(k-r)}{2k}}$

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 $A_{1},\dots ,A_{k}$ halmazból áll, ahol $|A_{1}|=\cdots =|A_{r}|=q+1$, $|A_{r+1}|=\cdots =|A_{k}|=q$, 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 $e\leq {\frac {n^{2}}{4}}$ teljesül.

Első bizonyítás

Legyenek a csúcsok $v_{1},\dots ,v_{n}$. Tegyük fel, hogy a $v_{i}$ és a $v_{j}$ csúcsok össze vannak kötve. A további $n-2$ pont egyike sem lehet mindkettővel összekötve. Ezen $n-2$ pontból $d(v_{i})-1$ és $d(v_{j})-1$ van összekötve $v_{i}$-vel, illetve $v_{j}$-vel (ahol $d(v)$ a v pont foka). Mivel egyik sem lehet mindkettővel összekötve, kapjuk, hogy

$(d(v_{i})-1)+(d(v_{j})-1)\leq n-2$

azaz

$d(v_{i})+d(v_{j})\leq n$

Ezt minden összekötött pontpárra összeadva a jobb oldal en lesz, a bal oldalban pedig minden $d(v_{i})$ tag annyiszor szerepel, ahány élben $v_{i}$ van, azaz $d(v_{i})$-szor. Tehát

$d(v_{1})^{2}+\cdots +d(v_{n})^{2}\leq en$

adódik.

A számtani és négyzetes közép közötti egyenlőtlenséget felhasználva

$\left({\frac {d(v_{1})+\cdots +d(v_{n})}{n}}\right)^{2}\leq {\frac {d(v_{1})^{2}+\cdots +d(v_{n})^{2}}{n}}.$

Mivel $d(v_{1})+\cdots +d(v_{n})=2e$, a fenti egyenlőtlenséget így alakíthatjuk:

$\left({\frac {2e}{n}}\right)^{2}\leq e$

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:

$e\leq \sum _{v\in B}d(v)\leq |B|k=(n-k)k\leq \left({\frac {n}{2}}\right)^{2},$

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

${{r} \choose {2}}={\frac {k-1}{2k}}r^{2}-{\frac {r(k-r)}{2k}},$

amint azt kiszorzással láthatjuk.

Tegyük fel, hogy q>0 és adott egy n szögpontú és maximális élszámú $K_{k+1}$-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 $e=a+b+c$. Mivel A teljes gráf,

$a={{k} \choose {2}}.$

Az indukció miatt azt is tudjuk, hogy

$b\leq {\frac {k-1}{2k}}(n-k)^{2}-{\frac {r(k-r)}{2k}}.$

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 $c\leq (n-k)(k-1)$.

Összeadva adódik

${{k} \choose {2}}+{\frac {k-1}{2k}}(n-k)^{2}-{\frac {r(k-r)}{2k}}+(n-k)(k-1)$

ami, mint kiszorzással látható, azonos a következővel:

${\frac {k-1}{2k}}n^{2}-{\frac {r(k-r)}{2k}}.$

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ú $B_{1},\dots ,B_{k}$ halmazokra és pontosan a különböző halmazokban levő csúcsok vannak összekötve. Két különböző $B_{i}$-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 $B_{i}$-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 $a_{1},\dots ,a_{k}$-ként, hogy $B_{i}$ elemei pontosan $a_{i}$-be nincsenek bekötve. De ezzel azt kapjuk, hogy gráfunk a $T(n,k)$ Turán-gráf az $B_{1}\cup \{a_{1}\},\dots ,B_{k}\cup \{a_{k}\}$ osztályokkal.