Satz von Mantel

Lehrsatz des mathematischen Teilgebiets der Graphentheorie, benannt nach W. 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.[1][2][A 1]

Formulierung des Satzes

Bearbeiten

Der Satz lässt sich zusammengefasst angeben wie folgt:[1]

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.[A 2]

Verwandter Satz

Bearbeiten

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:[3][4]

Sei   ein endlicher schlichter Graph der Knotenzahl   und der Kantenzahl   und sei weiter vorausgesetzt, dass   keinen Kreisgraphen des Typs   enthalte.
Dann ist die Ungleichung
 [A 3]
erfüllt.

Hintergrund

Bearbeiten

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.[A 4] Letztere lassen sich angeben wie folgt:[5]

Gegeben sei eine endliche Menge   sowie ein Teilmengensystem   und dazu der Hypergraph  .
Dabei sei   die zugehörige  -Gradfunktion.
Dann gelten folgende Formeln:
(i)   .[A 5]
(ii)   .

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b Stasys Jukna: Extremal Combinatorics. 2011, S. 56 ff., S. 63.
  2. László Lovász: Combinatorial Problems and Exercises. 1979, S. 68, S. 395.
  3. Stasys Jukna: Extremal Combinatorics. 2011, S. 25–26.
  4. Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise . 2018, S. 224–225.
  5. Stasys Jukna: Extremal Combinatorics. 2011, S. 9.

Anmerkungen

Bearbeiten
  1. Wie Stasys Jukna hervorhebt, ist der Mantel’sche Satz ein schönes Resultat (beautiful result), für den (mindestens) vier verschiedene Beweise existieren.
  2. Nimmt man für geradzahliges   den vollständig bipartiten Graph   , so zeigt sich, dass diese Ungleichung scharf ist.
  3.   ist die Ganzzahl-Funktion.
  4. Auf ähnlichen Formeln beruht auch der Beweis zum Lemma von Corrádi. Die in beiden Fällen wesentlich herangezogene Beweismethode ist die Methode der doppelten Abzählung (englisch double counting).
  5. Diese Formel lässt sich als eine Verallgemeinerung des Handschlaglemmas auffassen.