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]

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

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

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

${\displaystyle 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 ${\displaystyle A_{1},\dots ,A_{k}}$ halmazból áll, ahol ${\displaystyle |A_{1}|=\cdots =|A_{r}|=q+1}$, ${\displaystyle |A_{r+1}|=\cdots =|A_{k}|=q}$, két pontot pontosan akkor kötünk össze, ha különböző osztályokban vannak.

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 ${\displaystyle e\leq {\frac {n^{2}}{4}}}$ teljesül.

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

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

azaz

${\displaystyle 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 ${\displaystyle d(v_{i})}$ tag annyiszor szerepel, ahány élben ${\displaystyle v_{i}}$ van, azaz ${\displaystyle d(v_{i})}$-szor. Tehát

${\displaystyle 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

${\displaystyle \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 ${\displaystyle d(v_{1})+\cdots +d(v_{n})=2e}$, a fenti egyenlőtlenséget így alakíthatjuk:

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

ami átrendezve éppen a bizonyítandó állí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:

${\displaystyle 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.

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

${\displaystyle {{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ú ${\displaystyle 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 ${\displaystyle e=a+b+c}$. Mivel A teljes gráf,

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

Az indukció miatt azt is tudjuk, hogy

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

Összeadva adódik

${\displaystyle {{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:

${\displaystyle {\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ú ${\displaystyle 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ő ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a_{1},\dots ,a_{k}}$-ként, hogy ${\displaystyle B_{i}}$ elemei pontosan ${\displaystyle a_{i}}$-be nincsenek bekötve. De ezzel azt kapjuk, hogy gráfunk a ${\displaystyle T(n,k)}$ Turán-gráf az ${\displaystyle B_{1}\cup \{a_{1}\},\dots ,B_{k}\cup \{a_{k}\}}$ osztályokkal.