Westfälische Wilhelms-Universität Münster

Fachbereich: Mathematik und Informatik

Planare Graphen

Kreuzungslemma und Charakterisierung planarer Graphen nachKuratowski

Andrea Vollmer

Seminar: Graphentheorie

Dr. Thomas Timmermann

Sommersemester 2015

Vortrag vom 22. Juni 2015

Inhaltsverzeichnis

1 Einleitung 1

2 Die Kreuzungszahl und eine erste Abschätzung 2

3 Das Kreuzungslemma 5

4 Charakterisierung planarer Graphen nach Kuratowski 74.1 Liste nicht planarer Graphen . . . . . . . . . . . . . . . . . . . . . . . . . 74.2 Das Kuratowski-Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.3 Anwendung des Kuratowski-Theorems . . . . . . . . . . . . . . . . . . . . 10

i

1 Einleitung

Während die Anfänge der Graphentheorie (z.B. das Königsberger Brückenproblem) be-reits im 18. Jahrhundert liegen, werden die meisten ihrer Fortschritte erst im letztenJahrhundert verzeichnet. So auch die Erkenntnisse und Sätze zu planaren Graphen, mitdenen ich mich in meinem Vortrag beschäftigt habe.In dieser Ausarbeitung soll es daher zunächst um die Kreuzungszahl von Graphen undmöglichen Abschätzungen gehen, um anschließend das lang vermutete Kreuzungslemmazu beweisen. Hierbei werde ich dem Buch der Beweise von Martin Eigner und GünterM. Ziegler folgen.In einem zweiten großen Abschnitt wird es um die Charakterisierung planarer Gra-phen nach Kuratowski gehen, wobei hier vor allem Vorarbeit für das doch erstaunlicheKuratowski-Theorem geleistet werden soll, was seinerzeit einen Durchbruch der Graphen-theorie darstellte. Dieser Teil folgt A Textbuch of Graph theory von Balakrishnan undRanganathan sowie Combinatorics and Graph theory von Harris, Hirst und Mossinghoff.

1

2 Die Kreuzungszahl und eine ersteAbschätzung

Zu Beginn müssen ein paar grundlegende Definitionen wiederholt sowie auf eine Propo-sition verwiesen werden, die bereits in einem früheren Vortrag bewiesen wurde und dieim späteren Verlauf bei der Abschätzung der Kreuzungszahl benötigt wird.

Definition 2.1. Ein Graph heißt planar, wenn er in die Ebene R2 gezeichnet werdenkann, ohne dass sich Kanten kreuzen.

Definition 2.2. Ein Graph heißt eben, wenn schon eine Zeichnung des Graphen im R2

ohne kreuzende Kanten vorliegt.

Aus der Eulerschen Polyederformel kann folgende Beziehung geschlussfolgert werden:

Proposition 2.3. Sei G = (V,E) ein Graph mit n Knoten und m Kanten. Ein ebenerGraph hat dann höchstens 3n-6 Kanten.

Nun gehen wir zum eigentlichen Teil dieses Kapitels über und beginnen mit der Defi-nition der Kreuzungszahl.

Definition 2.4. Die Kreuzungszahl kr(G) eines Graphen G ist die kleinste Anzahl vonKreuzungen, die für eine Zeichnung von G möglich ist.

Bemerkung 2.5. Mit der Definition der Kreuzungszahl folgt schon, dass kr(G) = 0 füreinen ebenen Graphen G gilt.

Im folgenden betrachten wir so genannte minimale Zeichnungen, d.h Zeichnungen, indenen es so wenig kreuzende Kanten, wie möglich gibt. Solch eine minimale Zeichnungerfüllt offenbar folgende Bedingungen:

1. Keine Kante kann sich selber kreuzen.

2. Kanten mit gemeinsamen Endknoten können sich nicht kreuzen.

2

2 Die Kreuzungszahl und eine erste Abschätzung

3. Zwei Kanten können sich nicht mehrmals kreuzen.

Diese Bedingungen lassen sich anhand der folgenden, kleinen Skizzen beweisen. Hierbeifindet man immer eine Repräsentation desselben Graphen mit weniger Kreuzungen:

Abbildung 2.1: Bedingungen für minimale Zeichnungen

Wir wollen nun eine erste Abschätzung der Kreuzungszahl finden und nehmen an, dassalle Zeichnungen die drei Bedingungen erfüllen.Sei nun also eine minimale Zeichnung eines Graphen G mit kr(G) Kreuzungen, n Eckenund m Kanten gegeben. Um eine untere Schranke für die Kreuzungszahl kr(G) festzule-gen, betrachten wir den Graphen H, der aus G entsteht, indem man zusätzlich zu denKnoten und Kanten von G die Kreuzungspunkte von G als neue Knoten in H und dieKantenstücke zwischen den Kreuzungspunkten von G als neue Kanten in H nimmt. Dannist H eben und einfach, da es keine kreuzende Kanten mehr gibt und die drei Bedingun-gen für minimale Zeichnungen erfüllt sind.Somit besitzt H nH = nG + kr(G) Knoten und mH = mG + 2kr(G) Kanten, weil jederneuer Knoten von Grad 4 ist. Nun lässt sich Proposition 2.3 auf H übertragen:

mH ≤ 3nH − 6

⇔ mG + 2kr(G) ≤ 3(nG + kr(G))− 6

⇔ kr(G) ≥ mG − 3nG + 6

Also haben wir unsere erste Abschätzung gefunden: kr(G) ≥ m− 3n+ 6

Aufgabe 2.6. Zeichnet den vollständigen Graphen K6 auf und erstellt eine minimaleZeichnung. Wie groß ist kr(K6)?

3

2 Die Kreuzungszahl und eine erste Abschätzung

Lösung: n = 6, m =15 ⇒ kr(G) ≥ m− 3n+ 6 = 15− 3 · 6 + 6 = 3

Unsere Abschätzung sagt uns also, dass es keine Einbettung des K6 mit weniger alsdrei Kreuzungen gibt.

Abbildung 2.2: Einbettung des K6 mit minimaler Anzahl an Kreuzungen

4

3 Das Kreuzungslemma

Diese erste Abschätzung der Kreuzungszahl ist sinnvoll, wenn die Kantenzahl m nur linearmit der Knotenzahl n wächst. Für den Fall, dass die Kantenzahl echt schneller wächstals die Knotenanzahl, kann man aber eine bessere untere Schranke für die Kreuzungszahlfinden, was uns zum Kreuzungslemma führt.

Lemma 3.1 (Das Kreuzungslemma). Sei G ein einfacher Graph mit n Ecken und mKanten und es gelte m ≥ 4n. Dann ist

kr(G) ≥ 164

m3

n2

Das Kreuzungslemma wurde bereits 1973 von Erdõs und Guy vermutet, wobei sieanstatt 1

64 nur eine Konstante c > 0 wählten. Auch als Leighton, Ajtai, Chvátal, Newbornund Szemerédi 1982 unabhängig voneinander die ersten Beweise mit dem Faktor 1

100

aufstellten, wurden diese erst anerkannt als Lásló Székely 1997 das Kreuzungslemmaauf mehrere geometrische Extremalprobleme anwendete. Der folgende Beweis beruht aufeinen Email-Austausch von Bernard Gazelle, Mich Sharir und Emo Welzl und ist eineAnwendung der probabilistischen Methode nach Erdõs und Rényi.

Beweis. Wir betrachten eine minimale Einbettung eines Graphen G und eine Wahr-scheinlichkeit p ∈ [0, 1]. Wir erzeugen einen Untergraphen von G, in dem wir die einzel-nen Ecken unabhängig voneinander mit der Wahrscheinlichkeit p auswählen. So erhaltenwir den induzierten Untergraphen Gp.Seien np, mp und Xp Zufallsvariablen, wobei np die Anzahl der Ecken in Gp, mp dieAnzahl der Kanten in Gp und Xp die Anzahl der Kreuzungen in Gp zählt.

Wir haben bereits gesehen, dass kr(G)−m+3n ≥ 6 für jeden Graphen G gilt. Darausfolgt insbesondere kr(G)−m+ 3n ≥ 0. Betrachten wir nun den Erwartungswert:

E(Xp −mp + 3np) ≥ 0

5

3 Das Kreuzungslemma

⇔ E(Xp)− E(mp) + 3E(np) ≥ 0 (wegen der Linearität)

Da eine Ecke mit Wahrscheinlichkeit p in Gp liegt, folgt E(np) = pn. Eine Kante liegtnur in Gp, wenn beide Ecken in Gp liegen und somit gilt E(mp) = p2m. Und es folgtE(Xp) = p4kr(G), da eine Kreuzung wiederum nur in Gp liegt, wenn alle ihre vier un-terschiedlichen beteiligten Ecken in Gp liegen. Somit erhalten wir:

p4kr(G)− p2m+ 3pn ≥ 0

⇔ kr(G)− mp2− 3n

p3≥ 0

⇔ kr(G) ≥ mp2

+ 3np3

Setze p := 4nm . Nach Voraussetzung gilt m ≥ 4n und somit ist p höchstens 4n

4n = 1.Man erhält:

kr(G) ≥ m( 4nm

)2− 3n

( 4nm

)3

⇔ kr(G) ≥ m3

42n2 − 3m3

43n2

⇔ kr(G) ≥ 164

m3

m2

6

4 Charakterisierung planarer Graphennach Kuratowski

4.1 Liste nicht planarer Graphen

Nun wollen wir eine Liste nicht planarer Graphen aufstellen, um Kriterien für Planaritätvon Graphen zu erkennen und Vorbereitung für das Kuratowski-Theorem zu leisten.Aus dem Vortrag zur Eulerschen Polyederformel wissen wir bereits, dass der vollständigeGraph K5 und der bipartite Graph K3,3 nicht planar sind. Da dies aber nur für den K5

bewiesen wurde, werde ich den Beweis für den K3,3 noch einmal vorstellen.

(a) K5 (b) K3,3

Abbildung 4.1: Die ersten nicht planaren Graphen auf unserer Liste

Beweis. Wir nehmen an, der K3,3 sei planar.Wir wissen, dass die Anzahl der Ecken n = 6 und die Anzahl der Kanten m = 9 = e ist.Die Eulersche Polyederformel besagt, dass n - e + f = 2 gilt und so folgt für die Anzahlder Flächen von K3,3 f = 5.Nun betrachten wir das durchschnittliche Verhältnis der Seiten pro Fläche: f = 2e

f =185 < 4.Da der K3,3 ein einfacher bipartiter Graph ist, hat jeder seiner Kreise mindestens dieLänge 4, d.h. jede Fläche ist mindestens von vier Kanten begrenzt. Somit haben wireinen Widerspruch zur durchschnittlichen Seitenanzahl pro Fläche. Also ist der K3,3

nicht planar.

7

4 Charakterisierung planarer Graphen nach Kuratowski

Um die Liste nicht planarer Graphen zu erweitern, fügen wir alle Graphen hinzu, dieden K5 oder K3,3 als Untergraphen enthalten. Denn wir wissen, dass ein Graph, der einennicht planaren Untergraphen enthält, nicht planar ist. Doch wie sieht das mit Graphenwie in Abb. 4.2 aus?

Abbildung 4.2: Beliebiger nicht planarer Graph

Es ist leicht zusehen, dass dieser Graph nicht planar ist, obwohl er weder den K5 nochden K3,3 als Untergraphen enthält.Um dies dennoch mit dem noch folgenden Kuratowski-Theorem zu begründen, ist nochein bisschen Vorarbeit nötig.

Definition 4.1. Sei G = (V,E). Eine Unterteilung einer Kante e = {u, v} ∈ E ist dasErsetzen dieser Kante durch zwei neue Kanten a und b, die die beiden Knoten u und vder entfernten Kante e mit einem neuen Knoten w /∈ V verbinden.H heißt Unterteilungsgraph von G, wenn H durch eine endliche Reihe von Unterteilungenvon G entsteht.

(a) Graph G (b) Graph H

Abbildung 4.3: H ist Unterteilungsgraph von G

Notation 4.2. Entsteht ein Untergraph des Graphen G durch Entfernen einer Kantee = {u, v} ∈ G, so schreiben wir G - e. Entsteht dieser Untergraph durch Kontraktioneiner Kante e = {u, v} ∈ G, d.h. durch das Verschmelzen (auch als Zusammenziehen

8

4 Charakterisierung planarer Graphen nach Kuratowski

bezeichnet) ihrer Endpunkte u und v, so schreiben wir G · e. Insbesondere schreiben wirG ·H, wenn dieser Untergraph durch Kontraktion eines Untergraphen H von G entsteht.

4.2 Das Kuratowski-Theorem

Theorem 4.3 (Kuratowski-Theorem). Ein Graph G=(V,E) ist genau dann planar, wenner keine Unterteilung von K5 oder K3,3 enthält.

Beweis. ⇒Wir nehmen an, dass der Graph G eine Unterteilung H von K5 oder K3,3 alsUntergraphen enthält.Da bereits gezeigt wurde, dass K5 und K3,3 nicht planar sind, folgt schon, dass die Un-terteilung H nicht planar ist. G enthält also einen nicht planaren Untergraphen und istsomit schon nicht planar.Also gilt: Ist G planar, so enthält er keine Unterteilung von K5 oder K3,3.

⇐ Diese Richtung ist deutlich schwieriger, sodass wir diesen Teil des Theorems ohneBeweis stehen lassen und stattdessen einen weiteren Satz (4.5) mit Erläuterungen nennenwerden, der in der Rückrichtung benutzt werden könnte und eine Beweisidee erkennenlässt.

Definition 4.4. Wenn G ·H = K, so nennen wir K eine Kontraktion von G oder sagen,dass G zu K zusammenziehbar ist.Wir nennen G zu K subzusammenziehbar, wenn G einen Untergraphen H enthält, derzu K zusammenziehbar ist. Dabei nennen wir K eine Subkontraktion von G.

(a) G (b) K

Abbildung 4.4: K ist Kontraktion von G

Satz 4.5. Ein Graph ist genau dann planar, wenn er nicht zu K5 oder K3,3 subzusam-menziehbar ist.

9

4 Charakterisierung planarer Graphen nach Kuratowski

Die Idee des Satzes soll kurz erläutert werden. Durch Entfernen von Knoten und an-schließener Kantenkontraktion kann man jeden nicht planaren Graphen G zu einem ein-facheren nicht planaren Graphen verkleinern. Dabei entfernt man solange Knoten unddie zugehörigen Kanten, bis der nächste Schritt den Graphen planar machen würde. Aufdiese Weise erhält man einen Untergraphen, der den K5 oder K3,3 darstellt. Somit ist Gsubzusammenziehbar zum K5 oder K3,3.Um dies anschaulich nochmal darzustellen, wollen wir anhand des Satzes 4.5 und dengerade genannten Schritten zeigen, dass der Petersen-Graph nicht planar ist.

4.3 Anwendung des Kuratowski-Theorems

Abbildung 4.5: Der Petersen-Graph P

Zunächst vereinfachen wir den Petersen-Graph P, indem wir einen beliebigen Knotenund seine zugehörigen Kanten entfernen. Wir nennen unseren neuen Graph nun P0. DasEntfernen eines weiteren Knotens würde P0 planar machen.

Abbildung 4.6: Der vereinfachte Petersen-Graph P0

Nun führen wir mehrere Kantenkontraktionen in P0 durch. Hierbei ziehen wir jeweils

10

4 Charakterisierung planarer Graphen nach Kuratowski

die drei Knoten, die von Grad 2 sind, auf einen ihrer zwei Nachbarn und erhalten denGraph in Abbildung 4.7.

Abbildung 4.7: P0 nach Kontraktionsschritt

Betrachtet man nun Anzahl und Grad der verbliebenen Knoten, fällt auf, dass alle sechsKnoten von Grad 3 sind. Dies lässt schon auf den K3,3 schließen und ist nach Verschiebender Knoten auch schnell zu sehen. Somit haben wir gezeigt, dass der Petersen-Graph Psubzusammenziehbar ist zum K3,3, da unser vereinfachter Graph P0 ein Untergraph vonP ist und zusammenziehbar zum K3,3 ist. Hiermit folgt, dass der Petersen-Graph nichtplanar ist.

11

Literaturverzeichnis

[BdB] Aigner, Martin; Ziegler, Günter M. Das Buch der Beweise, Springer: Berlin, Hei-delberg, 2015.

[BaRa] Blakrishnan, R.; Ranganathan, K. A textbook of Graph theory, Springer: NewYork, 2000.

[HaHiMo] Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J. Combinatorics andGraph theory, Springer: New York, 2008.

12