Turán-gráf
A Wikipédiából, a szabad enciklopédiából.
A Tm(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 éllel össze van kötve az 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).
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 tartalmazo olyan n csúcsú gráf, amely nem tartalmaz egy Km + 1 teljes gráfot. Vagyis, ha G n csúcsú és Km + 1-mentes, akkor .