Der Satz von Reiman, englisch Reiman's theorem, 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.[1]

Formulierung des Satzes

Bearbeiten

Der Satz von Reiman lässt sich formulieren wie folgt:[2][3][4]

Gegeben sei ein endlicher einfacher Graph   mit   Knoten und   Kanten.    
Weiter sei vorausgesetzt:
(B) In   sind keine Viererkreise als Teilgraphen enthalten.
Dann gilt die Ungleichung:
(U)     .[5]
Mit anderen Worten:
Hat   eine Kantenzahl   , welche die reelle Zahl   echt übersteigt, so muss in   mindestens ein Viererkreis als Teilgraph enthalten sein.

Beweisskizze

Bearbeiten

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

 .

  besteht also exakt aus all jenen Paaren   in dem Graphen  , für die der Knoten   mit den zwei weiteren Knoten   und   benachbart ist.

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

 

und damit

 

und dann

 

und schließlich

   .

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

Anmerkung

Bearbeiten

Die mit dem Satz gegebene Ungleichung ist scharf in dem Sinne, dass für   ein Graph   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.[6]

Siehe auch

Bearbeiten

Literatur

Bearbeiten

Einzelnachweise und Anmerkungen

Bearbeiten
  1. In der Graphentheorie ist ein Kreis der Länge 4 ein Graph, der zum Kreisgraphen   isomorph ist. Ein solcher wird kurz auch als Viererkreis bezeichnet. Siehe Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. 4. Auflage. Springer Spektrum, Berlin (u. a.) 2014, ISBN 978-3-662-44456-6, S. 210.
  2. Aigner-Ziegler: Das BUCH der Beweise. S. 210–211.
  3. Martin Aigner, Günter M. Ziegler: Proofs from THE BOOK. 2. Auflage. Springer Verlag, Berlin (u. a.) 1999, ISBN 3-540-63698-6, S. 128–129 (MR1723092).
  4. Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg / Dordrecht / London / New York 2011, ISBN 978-3-642-17363-9, S. 24–26 (MR2865719).
  5.     ist die Gaußklammerfunktion.
  6. Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise. 4. Auflage. Springer Spektrum, Berlin (u. a.) 2014, ISBN 978-3-662-44456-6, S. 210–211.