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 ${\displaystyle m}$ Knoten enthalten zu müssen.

Der Fall der Dreiecke

Es sei ${\displaystyle G}$ ein ungerichteter Graph mit ${\displaystyle 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):[1] Hat ein Graph ${\displaystyle G}$ mit ${\displaystyle n}$ Knoten keine Dreiecke, so hat er höchstens ${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor }$ Kanten.

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

Für kleine ${\displaystyle n}$ ist die Aussage klar:

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

• ${\displaystyle n=1}$ : Dieser Graph hat weder Kanten noch Dreiecke und es ist ${\displaystyle \left\lfloor {\frac {1^{2}}{4}}\right\rfloor =0}$ .
• ${\displaystyle n=2}$ : Solche Graphen haben keine Dreiecke und höchstens eine Kante; es ist ${\displaystyle \left\lfloor {\frac {2^{2}}{4}}\right\rfloor =1}$ .
• ${\displaystyle n=3}$ : Solche Graphen haben genau dann ein Dreieck, wenn die Kantenzahl 3 ist; und es ist ${\displaystyle \left\lfloor {\frac {3^{2}}{4}}\right\rfloor =2}$ .
• ${\displaystyle n=4}$ : Es ist ${\displaystyle \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 ${\displaystyle n}$ führt man die Aussage auf Graphen mit ${\displaystyle n-2}$ Knoten zurück, was dann einen Induktionsbeweis ermöglicht, wobei man gerade und ungerade ${\displaystyle n}$ unterscheiden muss. Hier soll nur der Fall für gerade ${\displaystyle n}$ kurz angedeutet werden:

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

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

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

Der Turán-Graph

Ein Dreieck ist der vollständige Graph ${\displaystyle K_{3}}$ . Es stellt sich daher die Frage, ob man eine Obergrenze für die Anzahl von Kanten eines Graphen, der keinen zu ${\displaystyle 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${\displaystyle T_{3}(7)}$

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

${\displaystyle \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 ${\displaystyle T_{m}(n)}$ daher ${\displaystyle n}$ Knoten hat. Die Anzahl der Kanten von ${\displaystyle T_{m}(n)}$ werde mit ${\displaystyle t_{m}(n)}$ bezeichnet. Man kann zeigen, dass

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

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

Der nebenstehende Turán-Graph ${\displaystyle T_{3}(7)}$ hat demnach ${\displaystyle {\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 ${\displaystyle 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:[2] Hat ein Graph ${\displaystyle G}$ mit ${\displaystyle n}$ Knoten keinen zu ${\displaystyle K_{m}}$ isomorphen Untergraphen (${\displaystyle m\geq 3}$ ), so hat er höchstens ${\displaystyle t_{m-1}(n)}$ Kanten. Jeder Graph ohne einen zu ${\displaystyle K_{m}}$ isomorphen Untergraphen mit ${\displaystyle n}$ Knoten und ${\displaystyle t_{m-1}(n)}$ Kanten ist isomorph zum Turán-Graphen ${\displaystyle T_{m-1}(n)}$ .

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

${\displaystyle \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 ${\displaystyle n}$ Knoten ohne einen zu ${\displaystyle K_{m}}$ isomorphen Untergraphen, die diesen Extremwert realisieren, isomorph zu ${\displaystyle T_{m-1}(n)}$ sind.

Ist ${\displaystyle m=3}$ und ${\displaystyle n}$ gerade, so ist ${\displaystyle 0\equiv n\,\mathrm {mod} \,2}$ und daher ${\displaystyle t_{2}(n)={\frac {(2-1)(n^{2}-0^{2})}{2\cdot 2}}+0={\frac {n^{2}}{4}}}$ . Ist ${\displaystyle n}$ ungerade, so ist ${\displaystyle 1\equiv n\,\mathrm {mod} \,2}$ und daher ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle m\geq 3}$ kann zu ${\displaystyle m\geq 2}$ abgeschwächt werden, auch wenn der dadurch entstehende Fall nicht sonderlich interessant ist. Ein Graph ohne einen zu ${\displaystyle K_{2}}$ isomorphen Untergraphen ist ein kantenloser Graph und tatsächlich ist ${\displaystyle t_{1}(n)=0}$ für alle ${\displaystyle n}$ . Auch die Fälle ${\displaystyle m\geq n}$ müssen nicht ausgeschlossen werden. Für ${\displaystyle m=n}$ ist ${\displaystyle r=1}$ in der oben für ${\displaystyle t_{m}(n)}$ angegebenen Formel, und es ist daher ${\displaystyle 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 ${\displaystyle n}$ Knoten genau dann einen zu ${\displaystyle K_{n}}$ isomorphen Untergraphen enthält, wenn er vollständig ist, denn ${\displaystyle K_{n}}$ hat ${\displaystyle {\frac {n(n-1)}{2}}}$ Kanten. Ist ${\displaystyle m=n+1}$ , so ist ${\displaystyle r=0}$ und daher ${\displaystyle t_{m}(n)={\frac {n(n-1)}{2}}}$ , ist ${\displaystyle m>n+1}$ so ist ${\displaystyle r=n}$ und daher ebenfalls ${\displaystyle t_{m-1}(n)={\frac {r(r-1)}{2}}={\frac {n(n-1)}{2}}}$ ; das heißt, in den Fällen ${\displaystyle m>n}$ kann der Graph so viele Kanten wie möglich haben, was klar ist, da er ohnehin keinen zu ${\displaystyle 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)

Einzelnachweise

1. Frank Harary: Graphentheorie. R. Oldenbourg, München 1974, ISBN 3-486-34191-X.
2. Béla Bollobás: Graph Theory, An Introductory Course. Springer Verlag, New York 1979, ISBN 0-387-90399-2, IV, §2, Theorem 6