Twierdzenie Turána

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}}=\left(1-{\frac {1}{r}}\right)\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\land (v,w)\notin E.$

Załóżmy, że teza jest fałszywa – wtedy uda się skonstruować graf $G'=(V',E')$ 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'$ usuwając wierzchołek $w$ i tworząc kopię wierzchołka $u$ z takim samym jak $u$ zbiorem sąsiadów (nazwijmy ją $u'$). Ponieważ nie ma krawędzi między $u$ i $u',$ to żadna klika w $G'$ nie zawiera obu wierzchołków. Stąd jeżeli $G$ nie zawierał kliki $K_{r+1},$ to również $G'$ jej nie zawiera. Jednocześnie $G'$ zawiera więcej krawędzi:

$|E'|=|E|-deg(w)+deg(u)>|E|.$

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

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

${\begin{aligned}|E'|&=|E|-(deg(u)+deg(v)-1)+2deg(w)\\&=|E|+\underbrace {deg(w)-deg(u)} _{\geqslant 0}+\underbrace {deg(w)-deg(v)} _{\geqslant 0}+1\geqslant |E|+1\end{aligned}}.$

Teza 1 jest więc prawdziwa.

Zdefiniujmy relację $u\sim v\iff (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\leqslant 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|\geqslant 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