Definíció: Az n pontú, k részes Turán-gráfot Tn,k-t úgy kapjuk, hogy az n elemű V csúcshalmazt k darab majdnem egyenlő részre osztjuk (azaz az egyes részek/osztályok elemszáma maximum 1-gyel különbözzön) és a különböző osztályok között az összes élt behúzzuk, míg az egyes osztályokon belül nincs él.
Megjegyzés: A fent definiált Tn,k egy izomorfia erejéig egyértelműen meghatározott gráf. A majdnem egyenlő részekre bontásoknál az előforduló osztály méreteknek n/k fel, illetve lekerekített értekei (n/k egész esetén ez egy lehetőség, n/k nem egész esetén ez kettő lehetőség az osztályméretre) közül kell kikerülni. Továbbá az egyes osztályméretekhez tartozó osztályok száma/multiplicitása is meghatározott.
A fontos észrevétel, hogy a Tn,k Turán-gráfban nincs k+1 elemű klikk. Valóban tetszőlegesen kivéve V-ből k+1 pontot a skatulya-elv szerint lesz két csúcs, amley a Turán-gráf definíciójában szereplő osztályozás ugyanazon osztályából kerül ki, így nincsenek összekötve, így kivett pont k+1-esünk nem klikk.
Tétel: (Turán-tétel)
Ha G egy n pontú egyszerű gráf és
|E(G)|>|E(Tn,k)|, akkor G tartalmaz k+1 elemű klikket.
Megjegyzés: ha k<=n, akkor |E(Tn,k)| egy n pontú teljes gráf és a tétel nyilvánvalóan igaz (feltétele nem teljesülhet).
Bizonyítás: Legyen G egy tetszőleges n pontú gráf k+1 elemű klikk nélkül. Belátjuk, hogy élsz'ama legfeljebb |E(Tn,k)|.
Legyen v a gráfunk egyik maximális fokú csúcsa. Legyen N a v csúcs szomszédainak halmaza (|N|=d(v)=D(G)). M legyen V(G)-N, azaz v és a nem-szomszédai által alkotott halmaz. G-t módosítsuk a következő módon: N-en belül minden maradjon úgy ahogy G-ben volt. M összes pontját kössük össze N összes pontjával. További él ne szereplejen a módosított G' gráfban.
1. Állítás: G'-ben sincs k+1 elemű klikk. Valóban: Vegyünk egy tetszőleges K klikket G'-ből. M pontjai között nincsenek élek, így M-ből maximum egy csúcs szerepelhet a klikkben. M pontjai ugyan úgy viszonyulnak a többi csúcshoz (N összes csúcsával összekötöttek mással nem). Így feltehető, hogy klikkünk M-beli (ha van ilyen) pontja éppen v. Azaz K része N U {v}-nek, ami által feszített rész G egy részgráfja, amiben nincs k+1 elemű klikk.
Persze így a G'|N=G|N gráfban nincs k elemű klikk
2. Állítás: G'-ben minden x csúcs foka legalább akkora mint G-beli foka. Valóban, ha x az M halmaz eleme, akkor szomszédsága N, azaz foka |N|=D(G). Ha x az N halmazban van, akkor szomszédos az összes M-beli csúccsal, továbbá N-beli szomszédság ugyanaz mint G-ben.
A 2. Állításból nyilván következik, hogy G' éleinek száma legalább akkora mint G éleinek száma.
A fenti módosítást G'-n belül is elvégezhetjük a G'|N részgráfra. Ekkor N-en belül kialakul egy M', N' halmaz. M-en és M'-n belül nincs él, de minden M-beli/M'-beli csúcs az M/M' halmazon kívül minden más csúccsal szomszédos. G|N' nem tartalmaz k-1 elemű klikket.
Az ötletet tovább iterálva M, M', M'', M''', ... halmazokba osztályozzuk V(G)-t. Ezek független ponthalmazok, de bármelyik csúcs osztályán kívül minden más csúccsal összekötött. Az osztályok száma legfeljebb k. (Miért?)
Lemma: Legyen k<=|V(G)|. Ha legfeljebb k osztályba soroljuk V(G)-t és pontosan a különböző osztálybeli csúcsokat kötjük össze, akkor kapunk a legkevesebb élt, ha pontosan k osztályba osztályozunk, továbbá az osztályok mérete majdnem azonos (azaz bármely két osztály mérete maximum eggyel tér el).
A lemma könnyen ellenőrizhető. Elég azt igazolni, hogyha gráfunk nem az előírt módon néz ki, akkor élszáma csökkenhető: k-nál kevesebb osztály esetén lennie kell legalább két elemű osztálynak, aminek továbbosztásával csökkenthetjük az élszámot. Ha k osztályunk van, de az egyek mérete legalább kettővel nagyobb mint egy másiké, akkor a nagyobbikból egy csúcsot a kisebbikbe téve ismét egy kevesebb élű gráfhoz jutunk.
Ebből adódik a tétel.
Turán Pál a K4-et nem tartalmazó gráfok élszámának becslését emelte ki. K4 a tetraéder csúcs-él gráfja. Mi a helyzet, ha más szabályos test gráfját tiltjuk? Akkor mennyi el lehet gráfunkban? A kocka esetét mind a mai napig nem sikerült megoldani a matematikusoknak. Kérdésével Turán Pál a gráfelmélet egy új ágát alapította meg. Ezt extremális kombinatorikának nevezzük. Egy fonts és érdekes eset a Turán Pál által felvetett kérdések sorában> Hány él lehet egy n pontú egyszerű gráfban, ha nincs benne 4 hosszú kör? Erről itt olvashatunk.
Turán Pál a XX. századi magyar matematika egyik kiemelkedő alakja. Munkássága az analízis, számelmélet, gráfelmélet fejlődésére is nagy hatással volt. Életrajza az interneten magyar, angol és magyar nyelven is megtalálható.