Satz von Mantel

Der Satz von Mantel , Vorlage:EnS, 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 $\frac{n^2}{4}$ Kanten.

Verwandter Satz

Vorlage:Hauptartikel

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\le \lfloor \frac{n}{4}\cdot (1+\sqrt{4n-3})\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 $ℱ\subseteq 𝒫(X)$ und dazu der Hypergraph $H=(X,ℱ)$.

Dabei sei $d:X\to {\mathbb{N}}_0,x\mapsto d(x):=|\{F\in ℱ\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 ℱ}|Y\cap F|(\mathrm{\forall }Y\subseteq X)$ .

(ii) $\sum _{x\in X}d(x{)}^2=\sum _{F\in ℱ}\sum _{x\in F}d(x)=\sum _{F_1\in ℱ}\sum _{F_2\in ℱ}|F_1\cap F_2|$ .

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur