Twierdzenie Turána

Szablon:Dopracować Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki $K_{r+1}.$

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 $n$-wierzchołkowych, które nie zawierają kliki $(r+1)$-wierzchołkowej, najwięcej krawędzi posiada graf Turána $T(n,r).$

Stąd wynika, że w dowolnym grafie $G$ takim, że $G$ ma co najwyżej $n$ wierzchołków oraz nie zawiera $(r+1)$-wierzchołkowej kliki, jest co najwyżej

$\frac{r-1}{r}\cdot \frac{n^2}{2}=(1-\frac{1}{r})\cdot \frac{n^2}{2}$

krawędzi.

Szczególnym przypadkiem (dla $r=2$) 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 $\lfloor n^2/4\rfloor .$

Dowód

Niech $G=(V,E)$ będzie $n$-wierzchołkowym grafem niezawierającym kliki $K_{r+1}$ takim, że $G$ ma maksymalną możliwą liczbę krawędzi.

Teza 1: W $G$ nie istnieją wierzchołki $u,v,w$ takie, że $(u,v)\in E,$ ale $(u,w)\notin E\wedge (v,w)\notin E.$

Załóżmy, że teza jest fałszywa – wtedy uda się skonstruować graf $G^{\prime }=(V^{\prime },E^{\prime })$ zawierający tyle samo wierzchołków co $G$ i niezawierający kliki $K_{r+1},$ ale mający więcej niż $G$ krawędzi.

Przypadek 1: $deg(w)<deg(u)$ lub $deg(w)<deg(v).$

Bez zmniejszenia ogólności, niech $deg(w)<deg(u).$ Tworzymy graf $G^{\prime }$ usuwając wierzchołek $w$ i tworząc kopię wierzchołka $u$ z takim samym jak $u$ zbiorem sąsiadów (nazwijmy ją $u^{\prime }$). Ponieważ nie ma krawędzi między $u$ i $u^{\prime },$ to żadna klika w $G^{\prime }$ nie zawiera obu wierzchołków. Stąd jeżeli $G$ nie zawierał kliki $K_{r+1},$ to również $G^{\prime }$ jej nie zawiera. Jednocześnie $G^{\prime }$ zawiera więcej krawędzi:

$|E^{\prime }|=|E|-deg(w)+deg(u)>|E|.$

Przypadek 2: $deg(w)⩾deg(u)$ oraz $deg(w)⩾deg(v).$

W tym przypadku tworząc $G^{\prime }$ usuwamy wierzchołki $u$ oraz $v$ i tworzymy dwie kopie wierzchołka $w:$ $w^{\prime }$ i $w^{″}.$ Ponownie, ponieważ nie ma krawędzi pomiędzy $w,$ $w^{\prime }$ i $w^{″},$ to w $G^{\prime }$ nie stworzymy kliki większej niż taka, która istniałaby już w $G.$ Zauważmy jednak, że i w tym przypadku $G^{\prime }$ ma więcej krawędzi:

$\begin{array}{cc}|E^{\prime }|& =|E|-(deg(u)+deg(v)-1)+2deg(w)\\ & =|E|+\underset{⩾0}{\underbrace{deg(w)-deg(u)}}+\underset{⩾0}{\underbrace{deg(w)-deg(v)}}+1⩾|E|+1\end{array}.$

Teza 1 jest więc prawdziwa.

Zdefiniujmy relację $u\sim v⟺(u,v)\notin E.$ 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 $G$ nie ma krawędzi między $u$ i $w$ oraz między $w$ i $v,$ to nie może być też krawędzi między $u$ i $v.$ Stąd wynika, że $G$ jest, dla pewnego $k$ pełnym grafem k-dzielnym, w którym podział wierzchołków odpowiada podziałowi na klasy abstrakcji relacji $\sim .$

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

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

Niech $G=(V,E)$ będzie pełnym grafem $k$-dzielnym, w którym istnieją części podziału $A$ i $B$ takie, że $|A|>|B|+1.$ Możemy zwiększyć liczbę krawędzi w $G,$ przenosząc wierzchołek ze zbioru $A$ do zbioru $B.$ Wskutek przeniesienia usuniemy z grafu $|B|$ krawędzi, jednocześnie dodając $|A|-1$ krawędzi. W ostatecznym rozrachunku dodajemy $|A|-1-|B|⩾1$ krawędzi, co dowodzi tezy 2.

Z powyższego dowodu wynika, że spośród grafów $n$-wierzchołkowych niezawierających kliki $K_{r+1},$ najwięcej krawędzi ma graf Turána $T(n,r).$

Zobacz też

• graf Turána