Planare Graphen und die Eulersche Formel

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was einen Graphen planar macht

Ein Graph ist planar genau dann, wenn er sich so auf ein flaches Blatt Papier zeichnen lässt, dass sich keine zwei Kanten kreuzen. Jeder Knoten wird zu einem Punkt, jede Kante zu einer Kurve, die ihre beiden Endpunkte verbindet, und Kurven dürfen sich nur in einem gemeinsamen Knoten treffen. Eine Zeichnung, die diese Regeln einhält, heißt ebene Zeichnung oder Einbettung des Graphen, und ein Graph zusammen mit einer festen Einbettung ist ein ebener Graph.

Der Unterschied zwischen den beiden Wörtern ist wichtiger, als es zunächst scheint. Planar ist eine Eigenschaft des Graphen: Gefragt wird, ob irgendeine kreuzungsfreie Zeichnung existiert. Eben beschreibt eine bestimmte Zeichnung. Ein Graph kann eine völlig gute ebene Zeichnung haben und zugleich hundert Zeichnungen voller Kreuzungen, und keine der schlechten Zeichnungen spricht gegen ihn. Der vollständige Graph K4 ist das übliche erste Beispiel. Als Quadrat mit beiden Diagonalen gezeichnet, kreuzen sich seine zwei Diagonalen. Verschiebt man einen Knoten in die Mitte des Dreiecks, das die anderen drei bilden, verschwindet jede Kreuzung, also ist K4 planar.

Die Abbildung führt auch das durchgehende Beispiel dieses Artikels ein, das Dreiecksprisma. Es hat ein äußeres Dreieck A, B, C, ein inneres Dreieck D, E, F, und drei Speichen verbinden A mit D, B mit E und C mit F:

V = {A, B, C, D, E, F}                                   6 Knoten
E = {AB, BC, CA, DE, EF, FD, AD, BE, CF}                  9 Kanten

Drei praktische Bemerkungen klären, wovon die Definition abhängt und wovon nicht. Erstens beeinflussen Schleifen und parallele Kanten die Planarität nie: Eine zweite Kopie einer Kante lässt sich als dünne Kurve direkt neben der ersten zeichnen und eine Schleife als kleiner Bogen neben ihrem Knoten. Ein Multigraph ist genau dann planar, wenn sein zugrunde liegender einfacher Graph es ist, und deshalb werden die Zählschranken weiter unten in diesem Artikel für einfache Graphen formuliert. Zweitens sind die Ebene und die Kugel austauschbar. Die stereographische Projektion macht aus einer Zeichnung auf einer Kugel eine Zeichnung in der Ebene und umgekehrt, also ist ein Graph genau dann planar, wenn er sich ohne Kreuzungen auf die Oberfläche einer Kugel zeichnen lässt. Drittens braucht man nie Kurven. Wagner 1936 und Fáry 1948 bewiesen unabhängig voneinander, dass jeder einfache planare Graph eine ebene Zeichnung besitzt, in der jede Kante eine gerade Strecke ist, ein Ergebnis, das meist Satz von Fáry genannt wird.

2. Flächen: die Gebiete, die eine Zeichnung erzeugt

Schneiden Sie eine ebene Zeichnung entlang ihrer Kanten aus dem Papier, und das Papier zerfällt in Stücke. Diese Stücke sind die Flächen der Zeichnung. Genau eine von ihnen ist unbeschränkt; sie heißt Außengebiet, und es beim Zählen zu vergessen, ist der häufigste Ausrutscher in diesem ganzen Thema. Das Dreiecksprisma hat fünf Flächen: das innere Dreieck D, E, F, drei viereckige Flächen A, B, E, D, B, C, F, E und C, A, D, F sowie das Außengebiet außerhalb des Dreiecks A, B, C.

Die Länge (oder der Grad) einer Fläche ist die Anzahl der Kanten, die man beim Umlaufen ihres Randes entlanggeht, mit einer Regel, die die Buchführung exakt hält: Eine Kante, die auf beiden Seiten dieselbe Fläche hat, etwa eine Kante eines Baumes, wird zweimal durchlaufen und zweimal gezählt. Mit dieser Regel trägt jede Kante genau zwei zur Summe bei, eine für jede ihrer Seiten, und die Flächen gehorchen einem eigenen Handschlaglemma:

Summe der Flächenlängen = 2e

Prisma:  3 + 4 + 4 + 4 + 3  =  18  =  2 × 9
         (inneres Dreieck, drei Vierecke, Außengebiet begrenzt von A, B, C)

Diese Identität ist das Handschlaglemma für Knoten aus dem Leitfaden zu Knoten und Kanten mit Flächen anstelle von Knoten, und auf ihr beruht jede Schranke in den Abschnitten 4 und 5. Flächen gehören zu einer Zeichnung und nicht zum Graphen, also kann ein Graph mit mehreren ebenen Zeichnungen in jeder davon Flächen anderer Längen haben. Verbinden Sie zwei Knoten x und y durch vier Wege der Längen 1, 2, 3 und 4. Ordnet man sie in dieser Reihenfolge um x an, begrenzen aufeinanderfolgende Wege Flächen der Längen 3, 5, 7 und 5. Vertauschen Sie die beiden mittleren Wege, und die Flächenlängen werden zu 4, 5, 6 und 5. Was sich nicht ändert, ist die Anzahl der Flächen, vier in beiden Zeichnungen, und der nächste Abschnitt beweist, dass das kein Zufall ist.

3. Die Eulersche Formel

Zählen Sie die Knoten, Kanten und Flächen einer beliebigen zusammenhängenden ebenen Zeichnung, und eine Kombination der drei ändert sich nie.

Eulersche Formel. Für jeden zusammenhängenden ebenen Graphen mit v Knoten, e Kanten und f Flächen gilt v − e + f = 2.

Für das Prisma gilt 6 − 9 + 5 = 2. Für den kreuzungsfrei gezeichneten K4 gilt 4 − 6 + 4 = 2. Für einen einzelnen Knoten gilt 1 − 0 + 1 = 2, denn die leere Ebene um ihn herum ist eine Fläche. Der Beweis ist kurz genug, um ihn vollständig anzugeben, und es lohnt sich, ihn zu lesen, denn dieselbe Idee, eine Kante zu löschen und zu beobachten, was sich ändert, zieht sich durch das ganze restliche Thema.

Beweis. Halten Sie die Anzahl der Knoten fest und führen Sie eine Induktion über die Anzahl der Kanten. Ein zusammenhängender Graph mit so wenigen Kanten wie möglich ist ein Baum, und für einen Baum gilt e = v − 1 (eine der Charakterisierungen, die im Leitfaden zu Bäumen in der Graphentheorie gesammelt sind). Ein Baum enthält keinen Kreis, also umschließt seine Zeichnung kein Gebiet, und es gibt genau eine Fläche. Dann gilt v − (v − 1) + 1 = 2, wie behauptet.

Ist der zusammenhängende Graph kein Baum, enthält er einen Kreis. Wählen Sie eine Kante auf diesem Kreis und löschen Sie sie. Der Graph bleibt zusammenhängend, weil der Rest des Kreises die beiden Enden der gelöschten Kante weiterhin verbindet. In der Zeichnung ist der Kreis eine geschlossene Kurve, und nach dem jordanschen Kurvensatz zerlegt sie die Ebene in ein Inneres und ein Äußeres. Die gelöschte Kante hatte also auf ihren beiden Seiten verschiedene Flächen, eine innerhalb des Kreises und eine außerhalb, und ihr Entfernen verschmilzt diese beiden Flächen zu einer. Also sinkt e um eins und f sinkt um eins, und v − e + f bleibt unverändert. Nach Induktionsvoraussetzung erfüllt der kleinere Graph die Formel, also auch der ursprüngliche.

Die Formel hat eine Folgerung, die man leicht überliest. Die Anzahl der Flächen, f = e − v + 2, hängt nur vom Graphen ab und nicht davon, wie er gezeichnet wird. Deshalb hatten die beiden Zeichnungen des Vier-Wege-Graphen aus Abschnitt 2 beide vier Flächen: Mit v = 8 und e = 10 hat jede ebene Zeichnung dieses Graphen 10 − 8 + 2 = 4 Flächen. Ist der Graph nicht zusammenhängend, teilen sich alle Teile das Außengebiet, und die Formel wird zu v − e + f = 1 + k für einen Graphen mit k Komponenten.

Die Formel lässt sich leicht maschinell prüfen. Die folgende Funktion nimmt eine kreuzungsfreie geradlinige Zeichnung, gegeben als Koordinaten, und umläuft jede Fläche, indem sie den Kanten folgt und an jedem Knoten stets zur nächsten Kante im Uhrzeigersinn abbiegt. Jede Kante hat zwei Seiten, und jede Seite wird genau einmal durchlaufen.

from math import atan2

def faces(pos, edges):
    """Umläuft die Flächen einer kreuzungsfreien geradlinigen Zeichnung eines zusammenhängenden Graphen."""
    nbrs = {v: [] for v in pos}
    for u, v in edges:
        nbrs[u].append(v)
        nbrs[v].append(u)
    for v, ws in nbrs.items():               # Nachbarn gegen den Uhrzeigersinn sortiert
        x, y = pos[v]
        ws.sort(key=lambda w: atan2(pos[w][1] - y, pos[w][0] - x))
    seen, found = set(), []
    for u, v in edges:
        for dart in ((u, v), (v, u)):        # jede Kante hat zwei Seiten
            face = []
            while dart not in seen:
                seen.add(dart)
                a, b = dart
                face.append(a)
                ws = nbrs[b]
                dart = (b, ws[ws.index(a) - 1])  # bei b zur nächsten Kante im Uhrzeigersinn abbiegen
            if face:
                found.append(face)
    return found

pos = {'A': (0, 4), 'B': (-3.5, -2), 'C': (3.5, -2),
       'D': (0, 1.6), 'E': (-1.4, -0.8), 'F': (1.4, -0.8)}
edges = [('A', 'B'), ('B', 'C'), ('C', 'A'), ('D', 'E'), ('E', 'F'),
         ('F', 'D'), ('A', 'D'), ('B', 'E'), ('C', 'F')]
fs = faces(pos, edges)
v, e, f = len(pos), len(edges), len(fs)
print(v, e, f, v - e + f)
# 6 9 5 2
print(sorted(len(face) for face in fs))
# [3, 3, 4, 4, 4]

Die fünf Flächenlängen sind genau die in Abschnitt 2 gezählten, und ihre Summe ist 18 = 2e. Dasselbe Umlaufverfahren, auf eine abstrakte Liste von Nachbarreihenfolgen statt auf Koordinaten angewandt, ist die Art, wie Planaritätsbibliotheken eine Einbettung speichern: Eine Einbettung eines Graphen ist durch die zyklische Reihenfolge der Kanten um jeden Knoten vollständig beschrieben, und diese Beschreibung heißt Rotationssystem.

Polyeder, und woher die Formel kam

Euler formulierte die Formel nicht für Graphen. Er formulierte sie für Polyeder, Körper, die von ebenen Flächen begrenzt werden, in einem Brief an Christian Goldbach im November 1750, und veröffentlichte sie in zwei Arbeiten in der Zeitschrift der Sankt Petersburger Akademie, in dem auf 1752 und 1753 datierten Band, der 1758 gedruckt wurde. Zeichnen Sie ein konvexes Polyeder in die Ebene, indem Sie durch eine seiner Flächen hindurchsehen, die dann zum Außengebiet wird, und seine Ecken, Kanten und Flächen werden zu den Knoten, Kanten und Flächen eines ebenen Graphen. Die fünf platonischen Körper liefern alle dieselbe Antwort:

Die Geschichte hat zwei bekannte Wendungen. René Descartes hatte eine gleichwertige Beziehung, formuliert über Winkel, in einem heute verlorenen Manuskript niedergeschrieben; eine Abschrift, die Leibniz 1675 oder 1676 in Paris anfertigte, wurde im neunzehnten Jahrhundert wiederentdeckt und 1859–60 veröffentlicht. Und Eulers eigenes Argument, das nacheinander Ecken vom Körper abschnitt, war nach heutigen Maßstäben kein vollständiger Beweis. Adrien-Marie Legendre gab 1794 den ersten vollständigen Beweis, mithilfe der Flächeninhalte von Polygonen auf einer Kugel, und Augustin-Louis Cauchy veröffentlichte 1813 einen weiteren, der das Polyeder zu einem Netz in der Ebene flach drückt und es Stück für Stück zerlegt, dem Geist nach nahe am obigen Argument. Imre Lakatos baute sein Buch Proofs and Refutations (1976) um die seltsamen „Polyeder“ herum auf, die die Formel brechen, etwa einen Bilderrahmen, dessen Oberfläche ein Loch hat. Die Geschichte der Graphentheorie stellt dieses Ergebnis neben Eulers anderen Gründungsbeitrag, die Brücken von Königsberg.

4. Wie viele Kanten kann ein planarer Graph haben?

Zusammen mit dem Handschlaglemma für Flächen wird die Eulersche Formel zu einer harten Grenze für die Anzahl der Kanten. Das Argument sind die nützlichsten drei Zeilen in der Theorie der planaren Graphen.

Satz. Ein einfacher planarer Graph mit v ≥ 3 Knoten hat höchstens 3v − 6 Kanten. Hat er außerdem keine Dreiecke, hat er höchstens 2v − 4 Kanten.

Beweis. Nehmen Sie eine ebene Zeichnung und nehmen Sie zunächst an, dass der Graph zusammenhängend ist. In einem einfachen Graphen mit mindestens drei Knoten hat jede Fläche mindestens die Länge 3: Eine Fläche der Länge 1 bräuchte eine Schleife und eine Fläche der Länge 2 zwei parallele Kanten, außer wenn der ganze Graph eine einzige Kante ist, was v ≥ 3 ausschließt. Summiert über alle Flächen ergibt sich 3f ≤ 2e. Die Eulersche Formel liefert f = 2 − v + e, also 3(2 − v + e) ≤ 2e, was sich zu e ≤ 3v − 6 umformen lässt. Hat der Graph keine Dreiecke, hat jede Fläche mindestens die Länge 4, also gilt 4f ≤ 2e und dieselbe Einsetzung liefert e ≤ 2v − 4. Einem unzusammenhängenden planaren Graphen kann man Kanten zwischen seinen Komponenten hinzufügen, ohne eine Kreuzung zu erzeugen, und das Hinzufügen von Kanten macht die Ungleichung nur schwerer erfüllbar, also gelten die Schranken auch für ihn.

Die zweite Schranke deckt jeden bipartiten Graphen ab, denn ein bipartiter Graph hat keine ungeraden Kreise und insbesondere keine Dreiecke. Beide Schranken sind Spezialfälle einer einzigen Ungleichung. Hat der kürzeste Kreis in einem zusammenhängenden planaren Graphen, seine Taillenweite, die Länge g, dann hat jede Fläche mindestens die Länge g, und dieselben drei Zeilen liefern

e ≤ g(v − 2) / (g − 2)

g = 3   →   e ≤ 3v − 6        (jeder einfache planare Graph, v ≥ 3)
g = 4   →   e ≤ 2v − 4        (keine Dreiecke, also jeder bipartite planare Graph)
g = 5   →   e ≤ 5(v − 2)/3     (keine Kreise der Länge 3 oder 4)

Die erste Schranke wird erreicht. Ein ebener Graph, in dem jede Fläche, auch die äußere, ein Dreieck ist, heißt Triangulierung, und für eine Triangulierung wird 3f = 2e mit Gleichheit erfüllt, also gilt e = 3v − 6 exakt. Das Oktaeder (6 Knoten, 12 Kanten) und das Ikosaeder (12 Knoten, 30 Kanten) sind Triangulierungen. Fügt man einer Triangulierung irgendeine Kante hinzu, wird sie nicht planar, und deshalb heißen Triangulierungen auch maximal planare Graphen. Das Prisma ist nicht maximal: Es hat 9 Kanten bei einer Obergrenze von 3 × 6 − 6 = 12, und drei Diagonalen, eine in jeder viereckigen Fläche, würden es auf 12 bringen.

Zwei Folgerungen werden ständig gebraucht. Die erste ist, dass planare Graphen dünn besetzt sind: Die Anzahl der Kanten wächst nur linear mit der Anzahl der Knoten, also hat ein planarer Graph mit einer Million Knoten weniger als drei Millionen Kanten, während ein allgemeiner Graph mit einer Million Knoten fast 500 Milliarden haben kann. Deshalb misst man Algorithmen auf planaren Graphen an v allein, und deshalb sind Adjazenzlisten statt Matrizen das natürliche Speicherformat, wie im Artikel zur Darstellung von Graphen besprochen. Die zweite ist das Grad-fünf-Lemma:

Jeder einfache planare Graph hat einen Knoten vom Grad höchstens 5.

Die Summe der Grade ist 2e, und 2e ≤ 6v − 12 gilt, wenn v ≥ 3, also liegt der Durchschnittsgrad unter 6, und irgendein Knoten muss Grad 5 oder weniger haben. Graphen mit einem oder zwei Knoten erfüllen das Lemma trivialerweise. Das Lemma ist scharf: Jeder Knoten des Ikosaeders hat genau den Grad 5. Es ist der Motor hinter den Färbungssätzen in Abschnitt 8.

5. Warum K₅ und K₃,₃ nicht planar sind

Die Kantenschranken verwandeln „keine Zeichnung funktioniert“ von einer Aussage über unendlich viele Zeichnungen in eine einzeilige Rechnung.

Der vollständige Graph K5 hat v = 5 und e = 10. Ein planarer Graph mit 5 Knoten hat höchstens 3 × 5 − 6 = 9 Kanten, also ist K5 nicht planar.

Der vollständig bipartite Graph K3,3 hat v = 6 und e = 9. Die erste Schranke erlaubt 12 Kanten, sagt also nichts. Aber K3,3 ist bipartit und hat deshalb keine Dreiecke, und die zweite Schranke erlaubt nur 2 × 6 − 4 = 8. Neun Kanten sind eine zu viel. Das ist das klassische Drei-Versorger-Rätsel, das verlangt, drei Häuser so an Wasser, Gas und Strom anzuschließen, dass sich keine Rohre oder Kabel kreuzen. Es erscheint als „Water, Gas, and Electricity“ in Henry Dudeneys Amusements in Mathematics von 1917, und der Leitfaden zu bipartiten Graphen gibt dasselbe Argument von der bipartiten Seite aus.

Der Vergleich mit dem Prisma ist der lehrreiche Teil. Beide Graphen haben sechs Knoten und neun Kanten, und in beiden hat jeder Knoten den Grad 3, also kann keine Zählung von Knoten, Kanten oder Graden sie unterscheiden. Was sie trennt, ist die Form ihrer Flächen: Das Prisma kann zwei Dreiecke verwenden, während K3,3 für jede Fläche mindestens vier Seiten bräuchte, und dafür reicht der Platz nicht.

Beide Graphen sind nur knapp nicht planar. Jeder lässt sich mit genau einer Kreuzung zeichnen, wie die Abbildung zeigt, also ist ihre Kreuzungszahl gleich 1. Löscht man aus einem der beiden Graphen eine beliebige einzelne Kante, bleibt ein planarer Graph. Sie sind in einem präzisen Sinn die kleinsten Hindernisse für Planarität, und der nächste Abschnitt erklärt, dass sie die einzigen sind.

Die Zählschranken haben eine Grenze, die klar ausgesprochen werden muss: Sie sind notwendige Bedingungen, keine hinreichenden. Ein Graph, der sie verletzt, ist sicher nicht planar; ein Graph, der sie erfüllt, kann trotzdem nicht planar sein. Nehmen Sie K3,3 und fügen Sie eine Kante zwischen zwei Knoten derselben Seite hinzu. Der neue Graph hat 6 Knoten und 10 Kanten und enthält jetzt Dreiecke, also gilt nur die Schranke 3v − 6 = 12, und die erfüllt er. Trotzdem enthält er K3,3, also kann er nicht planar sein. Der Petersen-Graph liegt dazwischen. Mit 10 Knoten und 15 Kanten besteht er sowohl 3v − 6 = 24 als auch 2v − 4 = 16, aber seine Taillenweite ist 5, und die Taillenweitenschranke erlaubt nur 5 × 8 / 3, etwa 13,3, also 13 Kanten. Fünfzehn Kanten sind zu viele, und der Petersen-Graph ist nicht planar.

6. Die Sätze von Kuratowski und Wagner

Zwei Operationen setzen einen Graphen mit den kleinen Hindernissen in ihm in Beziehung. Eine Unterteilung eines Graphen ersetzt Kanten durch Wege und fügt entlang dieser neue Knoten vom Grad 2 ein. Das Unterteilen einer Kante ändert nichts daran, ob eine Zeichnung Kreuzungen hat, denn die neuen Knoten sitzen einfach auf der Kurve, also ist eine Unterteilung von K5 oder K3,3 genauso nicht planar wie das Original. Ein planarer Graph kann auch keinen nicht planaren Teilgraphen enthalten, denn das Löschen von Teilen einer ebenen Zeichnung hinterlässt eine ebene Zeichnung. 1930 bewies Kazimierz Kuratowski, dass diese offensichtlichen Hindernisse die einzigen sind.

Satz von Kuratowski (1930). Ein Graph ist genau dann planar, wenn er keinen Teilgraphen der folgenden Art enthält: eine Unterteilung von K5 oder von K3,3.

Die Richtung „nur dann“ ist die eben beschriebene leichte. Die Richtung „dann“ ist die tiefe: Jeder Graph, der sich nicht in der Ebene zeichnen lässt, muss eine dieser beiden Formen enthalten, möglicherweise mit Kanten, die zu langen Wegen gestreckt sind. Eine zweite Operation liefert eine sauberere Fassung. Das Kontrahieren einer Kante verschmilzt ihre beiden Enden zu einem Knoten, der zu allen ihren früheren Nachbarn adjazent ist, und ein Graph, den man aus G durch Löschen von Knoten und Kanten und Kontrahieren von Kanten erhält, ist ein Minor von G. Auch das Kontrahieren erhält die Planarität, denn man kann eine Kante einer ebenen Zeichnung zu einem Punkt schrumpfen lassen.

Satz von Wagner (1937). Ein Graph ist genau dann planar, wenn er weder K5 noch K3,3 als Minor hat.

Die beiden Sätze sind gleichwertig, aber in Beispielen nicht austauschbar, und der Petersen-Graph zeigt den Unterschied. Kontrahieren Sie die fünf Speichen, die seinen äußeren 5-Kreis mit seinem inneren Pentagramm verbinden, und die zehn Knoten fallen zu fünf zusammen, von denen jeder zu allen vier anderen adjazent ist: Der Petersen-Graph hat K5 als Minor. Er enthält jedoch keine Unterteilung von K5, denn eine Unterteilung von K5 braucht fünf Knoten vom Grad 4, und jeder Knoten des Petersen-Graphen hat den Grad 3. Der Satz von Kuratowski ist trotzdem erfüllt, durch die andere Form. Löschen Sie einen beliebigen Knoten, und die übrigen 9 Knoten und 12 Kanten bilden eine Unterteilung von K3,3: Drei der Knoten haben den Grad 2 und sitzen auf Wegen, und die anderen sechs zerfallen in zwei Seiten zu je drei.

Wagners Form eröffnete eine viel größere Geschichte. Planarität ist minorenabgeschlossen: Jeder Minor eines planaren Graphen ist planar. Neil Robertson und Paul Seymour bewiesen in einer Reihe von Arbeiten, die zwischen 1983 und 2004 erschienen, dass jede minorenabgeschlossene Graphenfamilie durch eine endliche Liste verbotener Minoren charakterisiert wird, so wie die planaren Graphen durch die Liste K5, K3,3 charakterisiert werden. Der Satz garantiert, dass eine solche Liste existiert und endlich ist, sagt aber nicht, wie lang die Liste ist oder wie man sie findet.

7. Planarität testen

Die Zählschranken aus Abschnitt 4 liefern einen sofortigen ersten Test. Sie können nicht beweisen, dass ein Graph planar ist, aber wenn ein Graph sie verletzt, beweisen sie, dass er es nicht ist, und ihre Prüfung kostet fast nichts. Die folgende Funktion berechnet die Taillenweite mit einer Breitensuche von jedem Knoten aus und wendet die Taillenweitenschranke an, die sowohl 3v − 6 als auch 2v − 4 als Spezialfälle enthält.

from collections import deque

def girth(adj):
    """Länge des kürzesten Kreises (inf für einen Wald): BFS von jedem Knoten aus."""
    best = float('inf')
    for s in adj:
        dist, parent = {s: 0}, {s: None}
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in dist:
                    dist[w], parent[w] = dist[u] + 1, u
                    queue.append(w)
                elif parent[u] != w:         # eine Nichtbaumkante schließt einen Kreis
                    best = min(best, dist[u] + dist[w] + 1)
    return best

def euler_filter(adj):
    """False: sicher nicht planar. True: nur 'nicht ausgeschlossen'. Einfache, zusammenhängende Graphen."""
    n = len(adj)
    m = sum(len(ws) for ws in adj.values()) // 2
    g = girth(adj)
    if g == float('inf'):
        return True                          # Bäume sind immer planar
    return m * (g - 2) <= g * (n - 2)        # g = 3 ergibt 3n - 6, g = 4 ergibt 2n - 4

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    return adj

prism = graph(['AB', 'BC', 'CA', 'DE', 'EF', 'FD', 'AD', 'BE', 'CF'])
k5 = graph([(i, j) for i in range(5) for j in range(i + 1, 5)])
k33 = graph([(a, b) for a in 'abc' for b in 'xyz'])
petersen = graph([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                 + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
k33_plus = graph([(a, b) for a in 'abc' for b in 'xyz'] + [('a', 'b')])
for name, adj in [('prism', prism), ('K5', k5), ('K3,3', k33),
                  ('Petersen', petersen), ('K3,3 + edge', k33_plus)]:
    print(f'{name:12} girth {girth(adj)}  passes: {euler_filter(adj)}')
# prism        girth 3  passes: True
# K5           girth 3  passes: False
# K3,3         girth 4  passes: False
# Petersen     girth 5  passes: False
# K3,3 + edge  girth 3  passes: True

Der Filter verwirft K5, K3,3 und den Petersen-Graphen, und er lässt das Prisma durch, was richtig ist, und K3,3 mit einer zusätzlichen Kante, was falsch ist. „passes“ bedeutet immer nur „nicht ausgeschlossen“. Jede Breitensuche braucht O(v + e) Zeit, und der Filter startet eine von jedem Knoten aus, also kostet er O(v(v + e)); ein Graph, der den billigeren Test e ≤ 3v − 6 nicht besteht, lässt sich verwerfen, bevor die Taillenweite überhaupt berechnet wird.

Eine vollständige Antwort braucht einen echten Planaritätsalgorithmus. Der Satz von Kuratowski liefert nicht direkt einen effizienten, denn die Suche nach Unterteilungen ist teuer. Hopcroft und Tarjan veröffentlichten 1974 den ersten in linearer Zeit laufenden Planaritätstest, aufbauend auf Tiefensuche, und spätere Algorithmen machten die Idee einfacher implementierbar: die Kantenhinzufügungsmethode von Boyer und Myrvold aus dem Jahr 2004 und das Links-Rechts-Planaritätskriterium von de Fraysseix und Rosenstiehl, auf dem die Implementierung in NetworkX beruht. Eine gute Implementierung liefert in beiden Fällen ein Zertifikat: eine ebene Einbettung, wenn der Graph planar ist, und einen Kuratowski-Teilgraphen, wenn nicht.

import networkx as nx

def count_faces(embedding):
    seen, f = set(), 0
    for u, v in embedding.edges():           # jede Halbkante liegt auf genau einer Fläche
        if (u, v) not in seen:
            embedding.traverse_face(u, v, mark_half_edges=seen)
            f += 1
    return f

tests = [('prism', nx.circular_ladder_graph(3)), ('K5', nx.complete_graph(5)),
         ('K3,3', nx.complete_bipartite_graph(3, 3)), ('Petersen', nx.petersen_graph()),
         ('K3,3 + edge', nx.complete_bipartite_graph(3, 3))]
tests[-1][1].add_edge(0, 1)
for name, G in tests:
    planar, cert = nx.check_planarity(G, counterexample=True)
    if planar:
        print(f'{name:12} planar, {count_faces(cert)} faces')
    else:
        branch = sum(1 for _, d in cert.degree() if d > 2)
        kind = 'K5' if branch == 5 else 'K3,3'
        print(f'{name:12} not planar: a subdivision of {kind}, '
              f'{cert.number_of_nodes()} vertices, {cert.number_of_edges()} edges')
# prism        planar, 5 faces
# K5           not planar: a subdivision of K5, 5 vertices, 10 edges
# K3,3         not planar: a subdivision of K3,3, 6 vertices, 9 edges
# Petersen     not planar: a subdivision of K3,3, 9 vertices, 12 edges
# K3,3 + edge  not planar: a subdivision of K3,3, 6 vertices, 9 edges

Jede Antwort kommt mit ihrem Beweis. Für das Prisma ist das Zertifikat eine Einbettung, gespeichert als Rotationssystem, und ihr Umlaufen ergibt 5 Flächen, wie es die Eulersche Formel verlangt. Für K5 und K3,3 ist das Zertifikat der ganze Graph. Für den Petersen-Graphen ist es eine Unterteilung von K3,3 mit 9 der 10 Knoten, genau die Struktur im rechten Feld der Abbildung oben, und es könnte nie eine Unterteilung von K5 sein, da kein Knoten den Grad 4 hat. Kuratowski-Teilgraphen sind nicht eindeutig, also kann eine andere Bibliothek oder Version einen anderen liefern; jeder von ihnen ist ein gültiger Beweis.

8. Planare Graphen färben und der Vierfarbensatz

Ihren berühmtesten Satz haben planare Graphen in der Färbung. Eine zulässige Färbung gibt jedem Knoten eine Farbe, sodass sich die beiden Enden jeder Kante unterscheiden, und die kleinste Anzahl von Farben, die genügt, ist die chromatische Zahl, die im Leitfaden zur Graphenfärbung ausführlich behandelt wird. Eine Landkarte so zu färben, dass sich benachbarte Länder unterscheiden, ist dasselbe Problem auf dem planaren Graphen der Karte, mit einem Knoten pro Land und einer Kante für jede gemeinsame Grenze.

Das Grad-fünf-Lemma aus Abschnitt 4 liefert bereits eine Schranke mit elementarem Beweis.

Sechsfarbensatz. Jeder planare Graph lässt sich zulässig mit höchstens sechs Farben färben.

Entfernen Sie einen Knoten vom Grad höchstens 5, den es nach dem Lemma gibt, und färben Sie den Rest des Graphen, der immer noch planar ist, per Induktion. Setzen Sie dann den Knoten zurück. Er hat höchstens fünf Nachbarn, also ist mindestens eine von sechs Farben für ihn frei. Der Beweis ist ein Algorithmus: Entfernen Sie wiederholt einen Knoten kleinsten Grades und färben Sie die Knoten dann in umgekehrter Reihenfolge ihrer Entfernung.

def six_colour(adj):
    """Färbt einen einfachen planaren Graphen mit höchstens 6 Farben (Greedy, kleinster Grad zuletzt)."""
    deg = {v: len(ws) for v, ws in adj.items()}
    removed, order = set(), []
    while len(order) < len(adj):
        v = min((u for u in adj if u not in removed), key=deg.get)  # ein Knoten mit Grad <= 5 existiert
        removed.add(v)
        order.append(v)
        for w in adj[v]:
            if w not in removed:
                deg[w] -= 1
    colour = {}
    for v in reversed(order):                # höchstens 5 Nachbarn sind schon gefärbt
        used = {colour[w] for w in adj[v] if w in colour}
        colour[v] = min(c for c in range(6) if c not in used)
    return colour

# Das Ikosaeder: 12 Knoten, 30 Kanten, jeder Knoten hat genau Grad 5.
edges = []
for i in range(5):
    j = (i + 1) % 5
    top, a, b, c, d, bottom = 0, 1 + i, 1 + j, 6 + i, 6 + j, 11
    edges += [(top, a), (a, b), (a, c), (a, d), (c, d), (c, bottom)]
adj = {v: [] for v in range(12)}
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
colour = six_colour(adj)
print(len(edges), {len(ws) for ws in adj.values()}, max(colour.values()) + 1)
# 30 {5} 4
print(all(colour[u] != colour[v] for u, v in edges))
# True

Auf dem Ikosaeder, wo jeder Knoten genau den Grad 5 hat, verwendet das Verfahren vier Farben, und das ist das Minimum, denn jeder Knoten braucht zusammen mit den fünf Nachbarn um ihn herum bereits vier. Die Reihenfolgeheuristik schneidet nicht immer so gut ab, aber sie braucht nie mehr als sechs.

Für fünf Farben braucht es eine weitere Idee. 1879 veröffentlichte Alfred Kempe einen Beweis, dass vier Farben immer genügen, beruhend auf dem Vertauschen der beiden Farben entlang einer Kette abwechselnd gefärbter Knoten, heute Kempe-Kette genannt. 1890 fand Percy Heawood einen Fehler in Kempes Argument und rettete in derselben Arbeit die Kettentechnik, um zu beweisen, dass fünf Farben immer genügen. Die Frage selbst geht auf 1852 zurück, als Francis Guthrie bemerkte, dass vier Farben für eine Karte der Grafschaften Englands ausreichten, und fragte, ob das immer so sei; sein Bruder Frederick gab die Frage an Augustus De Morgan weiter.

Vierfarbensatz (Appel und Haken, 1976). Jeder planare Graph lässt sich zulässig mit höchstens vier Farben färben.

Kenneth Appel und Wolfgang Haken kündigten den Beweis 1976 an und veröffentlichten ihn 1977. Er führt das Problem auf eine endliche Menge von Konfigurationen zurück, 1.482 in der veröffentlichten Fassung, und prüft jede davon per Computer, mit etwa 1.200 Stunden Rechenzeit. Es war der erste bedeutende Satz, dessen Beweis sich nicht von Hand prüfen ließ. Der Beweis wurde 1997 von Robertson, Sanders, Seymour und Thomas vereinfacht, die die Menge auf 633 Konfigurationen reduzierten, und 2005 vollendete Georges Gonthier einen vollständig formalen Beweis, Zeile für Zeile im Beweisassistenten Coq geprüft, der jeden verbliebenen Zweifel an der Computerarbeit ausräumte.

Vier ist die richtige Zahl: K4 ist planar und braucht vier Farben, weil alle vier seiner Knoten paarweise adjazent sind. Drei Farben reichen im Allgemeinen nicht, und zu entscheiden, ob sich ein gegebener planarer Graph mit drei Farben färben lässt, ist NP-vollständig, wie Garey, Johnson und Stockmeyer 1976 zeigten, selbst wenn jeder Knoten höchstens den Grad 4 hat. In der anderen Richtung bewies Grötzsch 1959, dass jeder planare Graph ohne Dreiecke 3-färbbar ist. Zwei Farben schließlich genügen genau für bipartite Graphen, ob planar oder nicht.

9. Duale Graphen

Jeder ebene Graph G hat einen Partner, sein Dual G*. Setzen Sie einen neuen Knoten in jede Fläche von G. Zeichnen Sie dann für jede Kante von G eine duale Kante, die sie kreuzt und die dualen Knoten der beiden Flächen auf ihren Seiten verbindet. Hat eine Kante auf beiden Seiten dieselbe Fläche, ist ihre duale Kante eine Schleife, und zwei Flächen, die mehrere Kanten gemeinsam haben, werden durch parallele duale Kanten verbunden, also ist das Dual im Allgemeinen ein Multigraph.

Das Prisma hat fünf Flächen, also hat sein Dual fünf Knoten. Der duale Knoten des inneren Dreiecks D, E, F ist mit den drei Vierecken verbunden, der duale Knoten des Außengebiets mit denselben drei, und die drei Vierecke sind untereinander zu einem Dreieck verbunden. Dieses Dual ist die dreiseitige Doppelpyramide, zwei dreiseitige Pyramiden, entlang ihrer Grundfläche zusammengeklebt: 5 Knoten, 9 Kanten und 6 dreieckige Flächen, eine Fläche für jeden der 6 Knoten des Prismas.

Die Dualität vertauscht die Rollen von Knoten und Flächen und behält die Kanten bei: G* hat f Knoten, e Kanten und v Flächen, also lautet die Eulersche Formel für beide gleich. Für zusammenhängende ebene Graphen ist das Dual des Duals wieder der ursprüngliche Graph. Die platonischen Körper bilden unter der Dualität Paare, der Würfel mit dem Oktaeder und das Dodekaeder mit dem Ikosaeder, während das Tetraeder zu sich selbst dual ist.

Das Dual übersetzt eine Art von Struktur in eine andere:

• Flächenfärbung wird zu Knotenfärbung. Die Gebiete einer Landkarte so zu färben, dass sich Nachbarn unterscheiden, ist dasselbe, wie die Knoten des dualen Graphen zu färben. So wird der Vierfarbensatz für Landkarten zu einer Aussage über planare Graphen.
• Kreise werden zu Schnitten. Die Kanten eines Kreises in G entsprechen einer minimalen Menge dualer Kanten, deren Entfernen G* unzusammenhängend macht, denn der Kreis trennt die Flächen in seinem Inneren von den Flächen außerhalb. In planaren Netzwerken wird so ein Problem des minimalen Schnitts zu einem Problem des kürzesten Kreises im Dual, einer der Gründe, warum maximaler Fluss auf planaren Graphen schneller geht als allgemein (siehe maximaler Fluss und minimaler Schnitt).
• Spannbäume bilden Paare. Ist T ein Spannbaum von G, dann bilden die Duale der nicht in T liegenden Kanten einen Spannbaum von G*. Das Abzählen der Kanten ergibt (v − 1) + (f − 1) = e, und das ist wieder die Eulersche Formel, aus einer völlig anderen Richtung.

Eine Warnung gehört zur Definition. Das Dual wird aus einer Zeichnung gebildet, nicht aus dem Graphen, also kann ein planarer Graph mit mehreren verschiedenen Einbettungen mehrere nicht isomorphe Duale haben. Whitney bewies 1932 und 1933, dass das bei 3-zusammenhängenden planaren Graphen nicht passieren kann, also bei solchen, die nach dem Löschen zweier beliebiger Knoten zusammenhängend bleiben: Ihre Einbettung auf der Kugel ist im Wesentlichen eindeutig, und damit auch ihr Dual. Das Prisma ist 3-zusammenhängend, und deshalb ist sein Dual wohldefiniert. Nach dem Satz von Steinitz sind die 3-zusammenhängenden planaren Graphen außerdem genau die Graphen konvexer Polyeder, und damit schließt sich der Kreis zurück zu Euler.

10. Wo planare Graphen vorkommen

Planarität ist eine geometrische Eigenschaft, also taucht sie überall dort auf, wo ein Netzwerk auf einer Oberfläche angeordnet werden muss, und überall dort, wo eine Oberfläche in Gebiete zerschnitten wird.

Schaltungen sind die klassische Anwendung. Auf einer einlagigen Leiterplatte können sich Kupferbahnen nicht kreuzen, ohne einen Kurzschluss zu verursachen, also muss der Verbindungsgraph planar sein. Ist er es nicht, führen Entwickler einige Bahnen auf einer zweiten Lage und verbinden die Lagen über gebohrte Löcher, sogenannte Vias, oder führen eine Bahn mit einer Drahtbrücke über eine andere. Die minimale Anzahl von Kreuzungen in irgendeiner Zeichnung eines Graphen, seine Kreuzungszahl, misst, wie stark eine Schaltung die Planarität verfehlt, und die Anzahl planarer Lagen, die nötig sind, um alle ihre Kanten aufzunehmen, ist ihre Dicke.

Landkarten liefern die zweite. Eine Karte von Ländern ist ein ebener Graph, dessen Flächen die Länder sind, und sein Dual hat einen Knoten pro Land und eine Kante pro gemeinsamer Grenze. Die Länder zu färben heißt, das Dual zu färben, und der Vierfarbensatz begrenzt die Anzahl der Farben auf vier, sofern jedes Land ein zusammenhängendes Gebiet ist. Echte Atlanten verletzen diese Bedingung: Ein Land aus getrennten Teilen, etwa die Vereinigten Staaten mit Alaska oder Russland mit Kaliningrad, muss an zwei Stellen dieselbe Farbe haben, und Karten mit solchen Bedingungen können mehr als vier Farben brauchen.

Straßennetze und Separatoren liefern die dritte. Lipton und Tarjan bewiesen 1979, dass sich jeder planare Graph mit n Knoten in zwei Teile zerlegen lässt, von denen keiner mehr als 2n/3 Knoten hat, indem man nur O(√n) Knoten entfernt. Kleine Separatoren sind die Grundlage von Teile-und-herrsche-Algorithmen auf planaren Graphen, und auch kürzeste Wege lassen sich so schneller berechnen. Straßennetze sind wegen Brücken und Tunneln nicht exakt planar, aber auch sie lassen sich meist durch das Entfernen weniger Knotenpunkte in große Stücke zerschneiden, und auf genau dieser Eigenschaft beruhen partitionsbasierte Routenplaner.

Polygonnetze liefern die letzte. Ein geschlossenes Dreiecksnetz einer kugelförmigen Oberfläche, ohne Lücken und ohne Henkel, erfüllt v − e + f = 2, und da jedes Dreieck drei Kanten hat und jede Kante an zwei Dreiecke grenzt, gilt 3f = 2e. Zusammen erzwingen diese f = 2v − 4 und e = 3v − 6. Ein Netz einer solchen Oberfläche, das diese Zahlen verfehlt, hat irgendwo eine Lücke, ein fehlendes Dreieck oder einen doppelten Knoten, und das macht die Zahlen zu einer billigen Plausibilitätsprüfung, wenn ein Netz importiert oder repariert wird.

11. Jenseits der Ebene: Kreuzungen und Oberflächen

Ein nicht planarer Graph ist nicht das Ende der Geschichte. Zwei naheliegende Fragen messen, wie weit er davon entfernt ist, planar zu sein.

Die erste ist die Kreuzungszahl cr(G), die kleinste Anzahl von Kreuzungen in irgendeiner Zeichnung. Planare Graphen haben die Kreuzungszahl 0, und K5 und K3,3 haben die Kreuzungszahl 1. Sie zu berechnen ist im Allgemeinen NP-schwer, und selbst für vollständige Graphen sind exakte Werte nur für kleine Fälle bekannt.

Die zweite ist, auf einer anderen Oberfläche zu zeichnen. Ein Torus, die Oberfläche eines ringförmigen Donuts, hat ein Loch, und das Loch gibt den Kanten einen Weg aneinander vorbei. Sowohl K5 als auch K3,3 lassen sich ohne Kreuzungen auf einen Torus zeichnen, und ebenso K7. Die Eulersche Formel lässt sich verallgemeinern: Ein Graph, der so auf eine Oberfläche mit g Löchern eingebettet ist, dass jede Fläche eine Scheibe ist, erfüllt

v − e + f = 2 − 2g

Ebene oder Kugel  g = 0:   v − e + f = 2
Torus             g = 1:   v − e + f = 0         K7 auf einem Torus:  7 − 21 + 14 = 0

Die Zahl 2 − 2g ist die Euler-Charakteristik der Oberfläche, eine der ersten Invarianten der Topologie. Heawood verwendete sie in seiner Arbeit von 1890, um die Anzahl der Farben zu beschränken, die auf einer Oberfläche mit g Löchern nötig sind, und Ringel und Youngs bewiesen 1968, dass die Schranke für jedes g ≥ 1 exakt ist. Für den Torus lautet die Antwort 7, und K7 zeigt, dass sieben Farben wirklich nötig sein können. Die Ebene, für die dieselbe Formel 4 ergäbe, war der eine Fall, den ihre Arbeit nicht abdeckte; das war der Vierfarbensatz.

12. Häufige Fehler

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53), 109 bis 140. Die Polyederformel, ohne Beweis formuliert.
2. Euler, L. (1758). "Demonstratio nonnullarum insignium proprietatum, quibus solida hedris planis inclusa sunt praedita." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53), 140 bis 160. Eulers Beweis durch das Abschneiden von Ecken.
3. Legendre, A.-M. (1794). Éléments de géométrie. Paris. Der erste vollständige Beweis, über sphärische Polygone.
4. Cauchy, A.-L. (1813). "Recherches sur les polyèdres. Premier mémoire." Journal de l'École Polytechnique 9 (16e cahier), 68 bis 86.
5. Kempe, A. B. (1879). "On the Geographical Problem of the Four Colours." American Journal of Mathematics 2(3), 193 bis 200.
6. Heawood, P. J. (1890). "Map-Colour Theorem." Quarterly Journal of Pure and Applied Mathematics 24, 332 bis 338. Der Fehler in Kempes Beweis, der Fünffarbensatz und die Schranke für andere Oberflächen.
7. Dudeney, H. E. (1917). Amusements in Mathematics. London: Thomas Nelson. Aufgabe 251, "Water, Gas, and Electricity."
8. Steinitz, E. (1922). "Polyeder und Raumeinteilungen." In Encyklopädie der mathematischen Wissenschaften, Band 3 (Geometrie), Teil 3AB12, 1 bis 139. Leipzig: Teubner.
9. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 bis 283.
10. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2), 339 bis 362. Kombinatorische Duale.
11. Whitney, H. (1933). "2-Isomorphic Graphs." American Journal of Mathematics 55, 245 bis 254. Eindeutigkeit der Einbettung 3-zusammenhängender planarer Graphen.
12. Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem." Jahresbericht der Deutschen Mathematiker-Vereinigung 46, 26 bis 32. Geradlinige Zeichnungen.
13. Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe." Mathematische Annalen 114, 570 bis 590. Planarität durch verbotene Minoren.
14. Fáry, I. (1948). "On Straight Line Representation of Planar Graphs." Acta Scientiarum Mathematicarum (Szeged) 11, 229 bis 233.
15. Grötzsch, H. (1959). "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel." Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe 8, 109 bis 120.
16. Ringel, G. und Youngs, J. W. T. (1968). "Solution of the Heawood Map-Coloring Problem." Proceedings of the National Academy of Sciences 60(2), 438 bis 445.
17. Hopcroft, J. und Tarjan, R. (1974). "Efficient Planarity Testing." Journal of the ACM 21(4), 549 bis 568.
18. Garey, M. R., Johnson, D. S. und Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3), 237 bis 267. Planare 3-Färbbarkeit ist NP-vollständig.
19. Lakatos, I. (1976). Proofs and Refutations: The Logic of Mathematical Discovery. Herausgegeben von J. Worrall und E. Zahar. Cambridge: Cambridge University Press.
20. Appel, K. und Haken, W. (1977). "Every Planar Map is Four Colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429 bis 490.
21. Appel, K., Haken, W. und Koch, J. (1977). "Every Planar Map is Four Colorable. Part II: Reducibility." Illinois Journal of Mathematics 21(3), 491 bis 567.
22. Lipton, R. J. und Tarjan, R. E. (1979). "A Separator Theorem for Planar Graphs." SIAM Journal on Applied Mathematics 36(2), 177 bis 189.
23. Federico, P. J. (1982). Descartes on Polyhedra: A Study of the De Solidorum Elementis. New York: Springer. Descartes' Manuskript und Leibniz' Abschrift.
24. de Fraysseix, H. und Rosenstiehl, P. (1985). "A Characterization of Planar Graphs by Trémaux Orders." Combinatorica 5(2), 127 bis 135. Das Links-Rechts-Kriterium.
25. Robertson, N., Sanders, D. P., Seymour, P. und Thomas, R. (1997). "The Four-Colour Theorem." Journal of Combinatorial Theory, Series B 70(1), 2 bis 44.
26. Boyer, J. M. und Myrvold, W. J. (2004). "On the Cutting Edge: Simplified O(n) Planarity by Edge Addition." Journal of Graph Algorithms and Applications 8(3), 241 bis 273.
27. Robertson, N. und Seymour, P. D. (2004). "Graph Minors. XX. Wagner's Conjecture." Journal of Combinatorial Theory, Series B 92(2), 325 bis 357.
28. Gonthier, G. (2008). "Formal Proof: The Four-Color Theorem." Notices of the American Mathematical Society 55(11), 1382 bis 1393.
29. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Springer. Kapitel 10 und 11 über planare Graphen und das Vierfarbenproblem.
30. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Kapitel 4 über planare Graphen.