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.