Twierdzenie Turána

Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki ${\displaystyle 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 ${\displaystyle n}$-wierzchołkowych, które nie zawierają kliki ${\displaystyle (r+1)}$-wierzchołkowej, najwięcej krawędzi posiada graf Turána ${\displaystyle T(n,r).}$

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

${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle \lfloor n^{2}/4\rfloor .}$

Dowód

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

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

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

Przypadek 1: ${\displaystyle deg(w)<deg(u)}$ lub ${\displaystyle deg(w)<deg(v).}$

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

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

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

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

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

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

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

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

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

Zobacz też

• graf Turána