Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki

Twierdzenie oraz pierwszy opis grafów Turána pochodzi od węgierskiego matematyka Pála Turána i zostało sformułowane w roku 1941. Pięć dowodów tego twierdzenia znajduje się w Dowodach z Księgi.

Sformułowanie Spośród wszystkich grafów -wierzchołkowych, które nie zawierają kliki -wierzchołkowej, najwięcej krawędzi posiada graf Turána

Stąd wynika, że w dowolnym grafie takim, że ma co najwyżej wierzchołków oraz nie zawiera -wierzchołkowej kliki, jest co najwyżej

krawędzi.

Uwaga. Szczególnym przypadkiem (dla ) twierdzenia Turána jest następujące twierdzenie Mantela: maksymalna liczba krawędzi w grafie bez trójkątów jest równa co najwyżej

Dowód Niech będzie -wierzchołkowym grafem niezawierającym kliki takim, że ma maksymalną możliwą liczbę krawędzi.

Teza 1: W nie istnieją wierzchołki takie, że ale

Załóżmy, że teza jest fałszywa – wtedy uda się skonstruować graf zawierający tyle samo wierzchołków co i niezawierający kliki ale mający więcej niż krawędzi.