Turán-gráf

A $T_m(n)$ n csúcsú, m osztályos Turán-gráf alatt a következő gráfot értjük:

Az ábrán egy-egy osztályban a csúcsok függetlenek, tehát nem fut közöttük él. Viszont, egy csúcs minden egyéb csúccsal össze van kötve a saját osztályán kivül (ezt jelzik a dupla párhuzamos vonalak). A pontok, annyira amennyire lehetséges, egyenletesen vannak szétosztva az osztályok között (emiatt vannak az alsó és felső egészértékek), vagyis bármely két osztály elemszámának eltérése legfeljebb 1..

Az ábrán szereplő gráfnak az a különleges tulajdonsága, hogy a Turán-féle gráftétel szerint ez a legtöbb élt tartalmazó olyan $n$ csúcsú gráf, amely nem tartalmaz egy $K_{m+1}$ teljes gráfot. Vagyis, ha $G$ $n$ csúcsú és $K_{m+1}$-mentes, akkor $|E(G)| \leq |E(T_m(n))|$.