Satz von Mantel

Der Satz von Mantel , englisch Mantel's theorem, ist einer der klassischen Lehrsätze des mathematischen Teilgebiets der extremalen Graphentheorie. Der Satz geht auf eine Arbeit von W. Mantel aus dem Jahre 1907 zurück und behandelt eine Bedingung, unter der ein Graph Dreiecke enthält.

Formulierung des Satzes

Der Satz lässt sich zusammengefasst angeben wie folgt:

Gegeben sei ein endlicher schlichter Graph $G=(V,E)$ der Knotenzahl $n=n(G)$ und der Kantenzahl $m=m(G)$.

Dabei soll die Ungleichung

$m>{\frac {n^{2}}{4}}$

erfüllt sein.

Dann enthält $G$ einen Kreisgraphen vom Typ $\,C_{3}\,$.

Anders gesagt:

Ist ein endlicher schlichter Graph der Knotenzahl $\,n\,$ dreiecksfrei, so besitzt er höchstens $\,{\tfrac {n^{2}}{4}}\,$ Kanten.

Verwandter Satz

→ Hauptartikel: Satz von Reiman

Von István Reiman (1927–2012) wurde im Jahre 1958 ein dem Mantel'schen verwandter Satz vorgelegt, welcher die entsprechende Fragestellung für den Kreisgraphen vom Typ $C_{4}$ behandelt. Dieser Satz lässt sich angeben wie folgt:

Sei $\,G\,$ ein endlicher schlichter Graph der Knotenzahl $\,n\,$ und der Kantenzahl $\,m\,$ und sei weiter vorausgesetzt, dass $\,G\,$ keinen Kreisgraphen des Typs $C_{4}$ enthalte.

Dann ist die Ungleichung

$m\leq \lfloor {\frac {n}{4}}\cdot \left(1+{\sqrt {4n-3}}\right)\rfloor$

erfüllt.

Hintergrund

Zum Beweis des Mantel’schen Satzes werden in der Monographie Extremal Combinatorics von Stasys Jukna sowohl die Cauchy-Schwarzsche Ungleichung als auch (nicht zuletzt) zwei elementare Formeln zu Mengensystemen auf endlichen Mengen herangezogen. Letztere lassen sich angeben wie folgt:

Gegeben sei eine endliche Menge $X$ sowie ein Teilmengensystem ${\mathcal {F}}\subseteq {\mathcal {P}}(X)$ und dazu der Hypergraph $H=(X,{\mathcal {F}})$.

Dabei sei $d\colon \,X\to \mathbb {N} _{0},\,x\mapsto d(x):=|\{F\in {\mathcal {F}}\mid x\in F\}|\,(x\in X)\,$ die zugehörige $H$-Gradfunktion.

Dann gelten folgende Formeln:

(i) $\sum _{x\in Y}d(x)=\sum _{F\in {\mathcal {F}}}|Y\cap F|\,\,\left(\forall Y\subseteq X\right)$ .

(ii) $\sum _{x\in X}{d(x)^{2}}=\sum _{F\in {\mathcal {F}}}\sum _{x\in F}d(x)=\sum _{F_{1}\in {\mathcal {F}}}\sum _{F_{2}\in {\mathcal {F}}}|F_{1}\cap F_{2}|$ .

Literatur

• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. Mit Zeichnungen von Karl H. Hofmann. 5. Auflage. Springer-Verlag, Berlin, Heidelberg 2018, ISBN 978-3-662-57766-0, doi:10.1007/978-3-662-57767-7. 
• Zoltán Füredi, András Gyárfás: An extension of Mantel’s theorem to k-graphs. In: American Mathematical Monthly. Band 127, 2020, S. 263–268 (MR4067898). 
• Frank Harary: Graphentheorie. R. Oldenbourg Verlag, München, Wien 1974, ISBN 3-486-34191-X. 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer-Verlag, Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9 (MR2865719). 
• László Lovász: Combinatorial Problems and Exercises (= Texts in Theoretical Computer Science). North-Holland Publishing Company, Amsterdam, New York, Oxford 1979, ISBN 0-444-85219-0 (MR0537284). 
• W. Mantel: Problem 28. In: Wiskundige Opgaven 10. Band 10, 1907, S. 60–61.