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{align} |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{align}$

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