Der Satz von Mantel , , ist einer der klassischen Lehrsätze des mathematischen Teilgebiets der extremalen Graphentheorie. Der Satz geht auf eine Arbeit von W. MantelSiehe Autorenprofil in zbMATH Open! aus dem Jahre 1907 zurück und behandelt eine Bedingung, unter der ein Graph Dreiecke enthält.Stasys Jukna: Extremal Combinatorics. 2011, S. 56 ff., S. 63.László Lovász: Combinatorial Problems and Exercises. 1979, S. 68, S. 395.Wie Stasys Jukna hervorhebt, ist der Mantel’sche Satz ein schönes Resultat (beautiful result), für den (mindestens) vier verschiedene Beweise existieren.
Formulierung des Satzes Der Satz lässt sich zusammengefasst angeben wie folgt: Gegeben sei ein endlicher schlichter Graph der Knotenzahl und der Kantenzahl . Dabei soll die Ungleichung
erfüllt sein. Dann enthält einen Kreisgraphen vom Typ . Anders gesagt: Ist ein endlicher schlichter Graph der Knotenzahl dreiecksfrei, so besitzt er höchstens Kanten.Nimmt man für geradzahliges den vollständig bipartiten Graph , so zeigt sich, dass diese Ungleichung scharf ist.
Verwandter Satz
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 behandelt. Dieser Satz lässt sich angeben wie folgt:Stasys Jukna: Extremal Combinatorics. 2011, S. 25–26.Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise . 2018, S. 224–225. Sei ein endlicher schlichter Graph der Knotenzahl und der Kantenzahl und sei weiter vorausgesetzt, dass keinen Kreisgraphen des Typs enthalte. Dann ist die Ungleichung ist die Gauß‘sche Abrundungsfunktion. 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.Auf ähnlichen Formeln beruht auch der Beweis zum Lemma von Corrádi. Die in beiden Fällen grundlegende Beweismethode ist die Methode der doppelten Abzählung (). Letztere lassen sich angeben wie folgt:Stasys Jukna: Extremal Combinatorics. 2011, S. 9. Gegeben sei eine endliche Menge sowie ein Teilmengensystem und dazu der Hypergraph . Dabei sei die zugehörige -Gradfunktion.
Dann gelten folgende Formeln:
(i) .Diese Formel lässt sich als eine Verallgemeinerung des Handschlaglemmas auffassen.
(ii) .
Literatur
Einzelnachweise
Anmerkungen
Mantel