Twierdzenie Turána

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 edytuj

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.

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 edytuj

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.
Przypadek 1:   lub  
Bez zmniejszenia ogólności, niech   Tworzymy graf   usuwając wierzchołek   i tworząc kopię wierzchołka   z takim samym jak   zbiorem sąsiadów (nazwijmy ją  ). Ponieważ nie ma krawędzi między   i   to żadna klika w   nie zawiera obu wierzchołków. Stąd jeżeli   nie zawierał kliki   to również   jej nie zawiera. Jednocześnie   zawiera więcej krawędzi:
 
Przypadek 2:   oraz  
W tym przypadku tworząc   usuwamy wierzchołki   oraz   i tworzymy dwie kopie wierzchołka     i   Ponownie, ponieważ nie ma krawędzi pomiędzy     i   to w   nie stworzymy kliki większej niż taka, która istniałaby już w   Zauważmy jednak, że i w tym przypadku   ma więcej krawędzi:
 
Teza 1 jest więc prawdziwa.

Zdefiniujmy relację   Jest to relacja równoważności – jest w oczywisty sposób zwrotna i symetryczna, natomiast przechodniość wynika z udowodnionej właśnie tezy 1, ponieważ jeżeli w   nie ma krawędzi między   i   oraz między   i   to nie może być też krawędzi między   i   Stąd wynika, że   jest, dla pewnego   pełnym grafem k-dzielnym, w którym podział wierzchołków odpowiada podziałowi na klasy abstrakcji relacji  

Zauważmy, że musi być   ponieważ w przeciwnym wypadku   zawierałby jako podgraf klikę   oraz że w pełnym grafie  -dzielnym liczba krawędzi rośnie wraz z   Stąd i z założenia, że   ma maksymalną liczbę krawędzi, wynika ostatecznie, że   i   jest pełnym grafem  -dzielnym.

Teza 2: Liczba krawędzi w pełnym grafie  -dzielnym jest maksymalna, kiedy wielkości części podziału zbioru wierzchołków różnią się co najwyżej o 1.

Niech   będzie pełnym grafem  -dzielnym, w którym istnieją części podziału   i   takie, że   Możemy zwiększyć liczbę krawędzi w   przenosząc wierzchołek ze zbioru   do zbioru   Wskutek przeniesienia usuniemy z grafu   krawędzi, jednocześnie dodając   krawędzi. W ostatecznym rozrachunku dodajemy   krawędzi, co dowodzi tezy 2.

Z powyższego dowodu wynika, że spośród grafów  -wierzchołkowych niezawierających kliki   najwięcej krawędzi ma graf Turána  

Zobacz też edytuj