Satz von Mantel

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 | Quelltext 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 | Quelltext 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.

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) .

Einzelnachweise

[Bearbeiten | Quelltext 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.
  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.