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.

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)\geq deg(u)$ oraz $deg(w)\geq 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)} _{\geq 0}+\underbrace {deg(w)-deg(v)} _{\geq 0}+1\geq |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\leq 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|\geq 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