Satz von Turán

Der Satz von Turán (nach Pál Turán) ist eine Aussage aus dem mathematischen Teilgebiet der Graphentheorie. Er macht eine Aussage über die maximale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl haben kann, ohne einen vollständigen Untergraphen mit $m$ Knoten enthalten zu müssen.

Der Fall der Dreiecke

Es sei $G$ ein ungerichteter Graph mit $n$ Knoten. Ein Untergraph aus drei Knoten heißt in naheliegender Weise ein Dreieck, wenn je zwei dieser drei Knoten durch eine Kante verbunden sind. Der Satz von Turán präzisiert die Aussage, dass der Graph, wenn er keine Dreiecke enthalten soll, nicht zu viele Kanten haben kann:

• Satz von Turán (Dreiecke): Hat ein Graph $G$ mit $n$ Knoten keine Dreiecke, so hat er höchstens $\left\lfloor {\frac {n^{2}}{4}}\right\rfloor$ Kanten.

Dabei ist $\lfloor x\rfloor$ die größte ganze Zahl, die kleiner gleich $x$ ist.

Für kleine $n$ ist die Aussage klar:

Graphen mit 4 Knoten und mindestens 5 Kanten enthalten mindestens ein Dreieck.

• $n=1$: Dieser Graph hat weder Kanten noch Dreiecke und es ist $\left\lfloor {\frac {1^{2}}{4}}\right\rfloor =0$.
• $n=2$: Solche Graphen haben keine Dreiecke und höchstens eine Kante; es ist $\left\lfloor {\frac {2^{2}}{4}}\right\rfloor =1$.
• $n=3$: Solche Graphen haben genau dann ein Dreieck, wenn die Kantenzahl 3 ist; und es ist $\left\lfloor {\frac {3^{2}}{4}}\right\rfloor =2$.
• $n=4$: Es ist $\left\lfloor {\frac {4^{2}}{4}}\right\rfloor =4$ und tatsächlich hat jeder 4er-Graph mit 5 Kanten mindestens ein Dreieck.

Für größere $n$ führt man die Aussage auf Graphen mit $n-2$ Knoten zurück, was dann einen Induktionsbeweis ermöglicht, wobei man gerade und ungerade $n$ unterscheiden muss. Hier soll nur der Fall für gerade $n$ kurz angedeutet werden:

Entfernt man a und b aus G so verbleiben nur die schwarzen Kanten.

Man entferne eine Kante, die zwei Knoten $a$ und $b$ verbindet, aus $G$. Der so erhaltene Untergraph enthält ebenfalls keine Dreiecke und nur $n-2$ Knoten, also gemäß Induktionsvoraussetzung höchstens $\left\lfloor {\frac {(n-2)^{2}}{4}}\right\rfloor ={\frac {(n-2)^{2}}{4}}$ Kanten. Der Graph $G$ hat darüber hinaus noch die entfernte Kante und weitere Kanten, die von $a$ oder $b$ ausgehen und in $G\setminus \{a,b\}$ enden. Gehen etwa $k$ von $a$ aus, so müssen die von $b$ ausgehenden Kanten in anderen Knoten von $G\setminus \{a,b\}$ enden, denn anderenfalls enthielte $G$ ein Dreieck, das heißt von $b$ können höchstens $n-2-k$ Kanten in $G\setminus \{a,b\}$ endende ausgehen. Die maximal mögliche Kantenzahl von $G$ ist daher ${\frac {(n-2)^{2}}{4}}+1+k+(n-2-k)\,=\,{\frac {n^{2}-4n+4}{4}}+1+n-2\,=\,{\frac {n^{2}}{4}}-n+1+1+n-2\,=\,{\frac {n^{2}}{4}}$. Daraus folgt die Behauptung für gerade $n$. Der Fall ungerader $n$ kann ganz ähnlich behandelt werden.

Die durch den Satz von Turán angegebene Grenze ist scharf, wie das Beispiel des bipartiten Graphen $K_{n,n}$ zeigt, denn dieser Graph hat $2n$ Knoten und $n^{2}={\frac {(2n)^{2}}{4}}$ Kanten.

Der Turán-Graph

Ein Dreieck ist der vollständige Graph $K_{3}$. Es stellt sich daher die Frage, ob man eine Obergrenze für die Anzahl von Kanten eines Graphen, der keinen zu $K_{m}$ isomorphen Untergraphen enthält, angeben kann. Um diese Frage beantworten zu können, wird der so genannte Turán-Graph wie folgt definiert:

Der Turán-Graph$T_{3}(7)$

Der Turán-Graph $T_{m}(n)$ ist der vollständige m-partite Graph, der in der k-ten Klasse $\left\lfloor {\frac {n+k-1}{m}}\right\rfloor$ Elemente hat. Beachte dazu, dass

$\left\lfloor {\frac {n}{m}}\right\rfloor +\left\lfloor {\frac {n+1}{m}}\right\rfloor +\ldots +\left\lfloor {\frac {n+m-1}{m}}\right\rfloor =n$

gilt und $T_{m}(n)$ daher $n$ Knoten hat. Die Anzahl der Kanten von $T_{m}(n)$ werde mit $t_{m}(n)$ bezeichnet. Man kann zeigen, dass

$t_{m}(n)={\frac {(m-1)(n^{2}-r^{2})}{2m}}+{\frac {r(r-1)}{2}}$

wobei $r\equiv n\,\mathrm {mod} \,m,\,\,0\leq r<m$ ist und $\mathrm {mod}$ für die Division mit Rest steht.

Der nebenstehende Turán-Graph $T_{3}(7)$ hat demnach ${\frac {(3-1)(49-1)}{2\cdot 3}}+{\frac {1\cdot (1-1)}{2}}={\frac {2\cdot 48}{6}}=16$ Kanten.

Eine leichte Rechnung zeigt $t_{m}(n)={\frac {n^{2}}{2}}\left(1-{\frac {1}{m}}+{\frac {r^{2}}{mn^{2}}}-{\frac {r}{n^{2}}}\right)\leq {\frac {n^{2}}{2}}\left(1-{\frac {1}{m}}\right)$. Diese obere Abschätzung der Kantenzahl des Turán-Graphen wird häufig verwendet.

Der allgemeine Fall

• Satz von Turán: Hat ein Graph $G$ mit $n$ Knoten keinen zu $K_{m}$ isomorphen Untergraphen ($m\geq 3$), so hat er höchstens $t_{m-1}(n)$ Kanten. Jeder Graph ohne einen zu $K_{m}$ isomorphen Untergraphen mit $n$ Knoten und $t_{m-1}(n)$ Kanten ist isomorph zum Turán-Graphen $T_{m-1}(n)$.

In der extremalen Graphentheorie definiert man zu einem Graphen $H$ die Zahl $\mathrm {ex} (n,H)$ als die maximale Kantenzahl, die ein Graph mit $n$ Knoten und ohne einen zu $H$ isomorphen Untergraphen haben kann. Der Satz von Turán hat daher folgendes Korollar:

$\mathrm {ex} (n,K_{m})\,=\,t_{m-1}(n)\leq {\frac {n^{2}}{2}}\cdot (1-{\frac {1}{m-1}})$

Der Satz von Turán sagt aber mehr aus, nämlich dass je zwei Graphen mit $n$ Knoten ohne einen zu $K_{m}$ isomorphen Untergraphen, die diesen Extremwert realisieren, isomorph zu $T_{m-1}(n)$ sind.

Ist $m=3$ und $n$ gerade, so ist $0\equiv n\,\mathrm {mod} \,2$ und daher $t_{2}(n)={\frac {(2-1)(n^{2}-0^{2})}{2\cdot 2}}+0={\frac {n^{2}}{4}}$. Ist $n$ ungerade, so ist $1\equiv n\,\mathrm {mod} \,2$ und daher $t_{2}(n)={\frac {(2-1)(n^{2}-1^{2})}{2\cdot 2}}+0={\frac {n^{2}-1}{4}}=\lfloor {\frac {n^{2}}{4}}\rfloor$. Daher ist $\mathrm {ex} (n,K_{3})\,=\,\lfloor {\frac {n^{2}}{4}}\rfloor$ und man erhält den bereits oben besprochenen Spezialfall der Dreiecke.

Die im Satz vorgenommene Einschränkung $m\geq 3$ kann zu $m\geq 2$ abgeschwächt werden, auch wenn der dadurch entstehende Fall nicht sonderlich interessant ist. Ein Graph ohne einen zu $K_{2}$ isomorphen Untergraphen ist ein kantenloser Graph und tatsächlich ist $t_{1}(n)=0$ für alle $n$. Auch die Fälle $m\geq n$ müssen nicht ausgeschlossen werden. Für $m=n$ ist $r=1$ in der oben für $t_{m}(n)$ angegebenen Formel, und es ist daher $t_{n-1}(n)={\frac {(n-2)(n^{2}-1)}{2(n-1)}}+0={\frac {(n-2)(n+1)}{2}}={\frac {n(n-1)}{2}}-1$; man erhält daher die triviale Aussage, dass ein Graph mit $n$ Knoten genau dann einen zu $K_{n}$ isomorphen Untergraphen enthält, wenn er vollständig ist, denn $K_{n}$ hat ${\frac {n(n-1)}{2}}$ Kanten. Ist $m=n+1$, so ist $r=0$ und daher $t_{m}(n)={\frac {n(n-1)}{2}}$, ist $m>n+1$ so ist $r=n$ und daher ebenfalls $t_{m-1}(n)={\frac {r(r-1)}{2}}={\frac {n(n-1)}{2}}$; das heißt, in den Fällen $m>n$ kann der Graph so viele Kanten wie möglich haben, was klar ist, da er ohnehin keinen zu $K_{m}$ isomorphen Untergraphen enthalten kann.

Literatur

• K. Wagner: Graphentheorie. Bibliographisches Institut, Mannheim 1970, ISBN 3-411-00248-4
• P. Turan: Eine Extremalaufgabe aus der Graphentheorie. In: Mat. Fiz. Lapok., 48, 1941, S. 436–452 (ungarisch)