Satz von Reiman

Der Satz von Reiman ist ein Lehrsatz aus dem mathematischen Teilgebiet der Kombinatorik, welche auf den ungarischen Mathematiker István Reiman (1927–2012) zurückgeht. Der Satz formuliert eine notwendige Bedingung dafür, dass ein endlicher einfacher Graph keine Kreise der Länge 4 als Teilgraphen enthält.

Formulierung des Satzes

Der Satz von Reiman lässt sich formulieren wie folgt:

Gegeben sei ein endlicher einfacher Graph ${\mathcal {G}}=(V,E)$ mit $|V|=n$ Knoten und $|E|=m$ Kanten.   $(n,m\in \mathbb {N} )$

Weiter sei vorausgesetzt:

(B) In ${\mathcal {G}}$ sind keine Viererkreise als Teilgraphen enthalten.

Dann gilt die Ungleichung:

(U) $m\leq \lfloor {{\frac {n}{4}}(1+{\sqrt {4n-3}})}\rfloor$   .

Mit anderen Worten:

Hat ${\mathcal {G}}$ eine Kantenzahl $m$ , welche die reelle Zahl ${\frac {n}{4}}(1+{\sqrt {4n-3}})$ echt übersteigt, so muss in ${\mathcal {G}}$ mindestens ein Viererkreis als Teilgraph enthalten sein.

Beweisskizze

Der Beweis beruht auf einer Anwendung der Methode des doppelten Abzählens, dem Handschlaglemma und der Ungleichung von Cauchy-Schwarz.

Hierbei geht man aus von der man die Menge

$S=\{(v_{0},\{v,w\})\mid {\bigl (}v_{0},v,w\in V{\bigr )}\land {\bigl (}v\neq w{\bigr )}\land {\bigl (}\{v_{0},v\},\{v_{0},w\}\in E{\bigr )}\}$.

$S$ besteht also exakt aus all jenen Paaren $(v_{0},\{v,w\})$ in dem Graphen ${\mathcal {G}}$, für die der Knoten $v_{0}$ mit den zwei weiteren Knoten $v$ und $w$ benachbart ist.

Für diese ergibt sich aufgrund von (B) im Zusammenhang mit den Graden der einzelnene Knoten nacheinander

$\sum _{v\in V}{\binom {d_{\mathcal {G}}(v)}{2}}=|S|\leq {\binom {n}{2}}$

und damit

$n\cdot \sum _{v\in V}{{d_{\mathcal {G}}(v)}^{2}}\leq n^{2}(n-1)+n\cdot \sum _{v\in V}{d_{\mathcal {G}}(v)}$

und dann

$\left(\sum _{v\in V}{d_{\mathcal {G}}(v)}\right)^{2}\leq n^{2}(n-1)+n\cdot \sum _{v\in V}{d_{\mathcal {G}}(v)}$

und schließlich

$4m^{2}\leq n^{2}(n-1)+2nm$  .

Aus der letzten Ungleichung jedoch gelangt man mittels quadratischer Ergänzung unmittelbar zur Ungleichung (U) .

Anmerkung

Die mit dem Satz gegebene Ungleichung ist scharf in dem Sinne, dass für $n=5$ ein Graph ${\mathcal {G}}$ mit fünf Knoten und sechs Kanten existiert, bei dem die Ungleichung zu einer Gleichung wird. Es handelt sich um einen Windmühlengraphen (englisch Windmill graph), der aus zwei Dreiecksgraphen (als Teilgraphen) gebildet wird, welche genau einen Knoten als Schnittpunkt haben.

Literatur

• Martin Aigner, Günter M. Ziegler: Proofs from THE BOOK. 2. Auflage. Springer Verlag, Berlin (u. a.) 1999, ISBN 3-540-63698-6.  MR1723092
• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. 4. Auflage. Springer Spektrum, Berlin (u. a.) 2014, ISBN 978-3-662-44456-6. 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Berlin - Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9.  MR2865719
• I. Reiman: Über ein Problem von K. Zarankiewicz. In: Acta Math. Acad. Sci. Hungar. Band 9, 1958, S. 269–273.  MR0101250 MR3184547
• Jonathan L. Gross - Jay Yellen (Hrsg.): Handbook of Graph Theory (= Discrete Mathematics and its Applications). CRC Press, Boca Raton (u.a.) 2004, ISBN 1-58488-090-2.