Graf Turána
Wygląd
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Turan_13-4.svg/220px-Turan_13-4.svg.png)
Graf Turána – graf powstały przez podział zbioru wierzchołków na możliwie równych części i połączenie krawędziami tych wierzchołków, które w wyniku podziału znajdą się w różnych podzbiorach.
W wyniku podziału zbioru wierzchołków powstaje podzbiorów zawierających elementów oraz podzbiorów -elementowych. Z samej definicji wynika, że jest zupełnym grafem r-dzielnym. Każdy wierzchołek jest stopnia albo Liczba krawędzi grafu wynosi w przybliżeniu:
Nazwa grafu pochodzi od nazwiska węgierskiego matematyka Pála Turána, który wykorzystywał własności takich grafów w dowodzie twierdzenia Turána dotyczącego oszacowania maksymalnej liczby krawędzi w grafie niezawierającym kliki