Anmerkungen zum Vierfarbensatz

Das Vierfarbenproblem hat mich seit vielen Jahren fasziniert. Ich habe mich inzwischen ausgiebig mit der Materie befasst und stelle hier das Ergebnis meiner Betrachtungen von „Lösungen“, dh. von gültigen Kantendrei- bzw. Flächenvierfärbungen beliebiger Landkarten vor. Ich habe einen graphischen Editor entwickelt, mit dessen Hilfe sich eine Fülle von interessanten Tatsachen und Zusammenhängen anschaulich darstellen lassen. Wegen der mit der Flächenzahl exponentiell steigenden Menge der Färbungsmöglichkeiten wird die Suche nach Lösungen als np-schweres Problem eingestuft. Suchalgorithmen sind weiter unten beschrieben. Man kann das Problem eines Beweises, das einen festen Platz in der modernen Graphentheorie erworben hat, aber auch ohne viel Mathematik in Worte fassen und verständlich darstellen, Mathematik zum Anfassen also.

Schon Leonhard Euler, Altmeister der Graphentheorie versuchte zu beweisen, dass für jede Karte wenigstens eine Lösung existieren müsste. Ich gehe davon aus, dass alle Landkarten Lösungen haben und werde versuchen nachzuweisen, dass es keine solche ohne eine einzige Lösung geben kann. Siehe weiter unten unter "Beweis". Appel und Haken haben einen „Computerbeweis“ vorgelegt, der inzwischen von der Fachwelt akzeptiert wird. Es bleibt aber ein gewisses Unbehagen, denn ein einfacher, klassischer Beweis „mit Papier und Bleistift“ steht nach wie vor aus. Die im Folgende beschriebenen Erkenntnisse und daraus abgeleiteten Schlussfolgerungen habe ich selbst erarbeitet. Ausser einigen allgemein bekannten und bewiesenen Formeln und Sätzen  habe ich keine fremden Darstellungen  benützt und deshalb auf Quellenangaben verzichtet.                                       

Jede Landkarte kann durch Strecken der Grenzabschnitte in einen ebenen Graphen überführt werden. Natürliche Landkarten haben bis auf ganz wenige Ausnahmen nur Dreiländerecken und sind dann drei-regulär. Sie enthalten nur Dreier-Ecken, und sind per Definition immer eben und kreuzungsfrei. Jeder ebene Graph kann drei-regulär gemacht werden, indem alle Ecken, an denen mehr als 3 Kanten zusammentreffen durch "Miniflächen" ersetzt werden. Anschaulicher: Man denke sich die Ecken des isomorphen Polyeders, an denen mehr als drei Kanten zusammentreffen abgeschnitten. Die so entstandenen Schnittflächen, die jetzt dreiregulär sind, werden nach erfolgreicher Färbung wieder zu einer Ecke zusammengezogen. Dann treffen zwar gleiche Flächenfarben an Ecken, aber nicht an Kanten zusammen.

Folgende Synonyme werden nebeneinander verwendet:

Man kann eine reale Landkarte falten, zusammenrollen, verzerren oder zusammenknüllen, ohne dass die Relation ihrer Elemente untereinander verändert wird, vorausgesetzt sie hat danach keine Löcher oder Risse. Das Gleiche gilt für die Projektion eines beliebigen Graphen g. Dieser enthalte nur n-Ecke mit einer Kantenzahl k≥4. Nullecke (Enklaven), Zweiecke (Doppelkanten) und Dreiecke kommen zwar in realen Landkarten vor, sind aber ohne Belang für die spätere Färbung und werden im Folgenden ausgeschlossen. Stellt man sich den Graphen als ein aus dehnbaren Gummifäden geknüpftes Netz vor, so kann man dieses in der Ebene aufspannen, indem man die Knoten einer Masche auf einem Kreis, z.B. einem runden Tisch an dessen Rand in etwa gleichen Abständen befestigt. Alle übrigen Knoten werden sich so auf der Tischplatte anordnen, dass Kräftegleichgewicht an ihren drei dort zusammentreffenden Fäden herrscht. Das Netz kann auch durch jede seiner Maschen kreuzungsfrei über eine Kugel gespannt werden. Wenn man die Kanten, die jetzt Kreisbögen sind, durch Geraden ersetzt, entsteht ein räumliches Stabwerk, das durch Verschieben der Ecken auf der Kugeloberfläche in einen isomorphen, konvexen Polyeder mit ebenen Flächen transformiert werden kann. Dabei ergeben sich genau so viele isomorphe Sichten auf den selben Graphen, wie das Netz Maschen hat. Das n-Eck, durch das die Projektion erfolgte, wird in der Ebene zur den Graphen umgebenden, ins Unendliche reichenden Fläche und muss in den folgenden Formeln immer mitgezählt werden. Eine Landkarte oder deren korrespondierender Graph G werden nicht als statische Objekte sondern das Ergebnis vielfältiger topologischer Prozesse betrachtet. 

Der Eulersche Polyedersatz:

k–e = f–2 

Mit k=Kantenzahl, e=Eckenzahl und f=Flächenzahl wird:
f'= (f-2) → e = 2f'; k = 3f' → f' : e : k = 1 : 2 : 3
Die Flächenzahl f ist das Mass für die „Grösse“ eines Graphen.

Genesis eines dreiregulären Graphen

Die Entstehung eines solchen Graphen lässt sich am besten auf der Kugeloberfläche veranschaulichen. Schliesslich beziehen sich ja alle Landkarten auf die Erdoberfläche. Am Anfang steht deren gesamte, ungeteilte Oberfläche: f=0; k=0; e=0 mit f=Anzahl der n-Ecke dieses Graphen. Im ersten Schritt wird diese durch eine geschlossene Linie zweigeteilt: f=2 (die "Urflächen"); k=0; e=0. Durch Einfügen einer Kante in eine der beiden Kugelschalen entsteht der erste dreireguläre "Urgraph, das Drei-Zweieck" mit f'=f-2 → f'=1; e=2: k=3. Im nächsten und allen folgenden Schritten wird jeweils eine Fläche durch Einziehen einer weiteren Kante zweigeteilt: f'=2; e=4: k=6 usw. Dadurch verschwinden bzw. entstehen bei jedem Schritt zusätzlich eine Fläche, zwei  Ecken und drei Kanten: die entfernte bzw. eingefügte plus die beiden durch Teilung der Anschlusskanten entstandenen. Der Eulersche Polyedersatz ist also in allen Schritten erfüllt.

Lösungen
Eine Lösung λi auf g sei eine Kanten-3-Färbung, bei der alle Kanten gefärbt sind und an keiner Ecke Kanten gleicher Farbe zusammentreffen. Die Abbildung einer Kanten-Dreifärbung mit den Farben {x,y,z} auf ihre äquivalente Flächen-Vierfärbung mit den Farben {a,b,c,d} ist umkehrbar und wird durch das Tetraederschema definiert:

Zu lesen:
Kantenfarbe x trennt
Flächenfarben a und b oder d und c,
usw. für die Kantenfarben y und z

Teilkreise

Wenn man in einer Lösung auf g, beginnend an einer beliebigen Ecke einem Kantenzug mit abwechselnd zwei der drei Kantenfarben, z.B. {x,y} folgt, so werden im Ausnahmefall alle Ecken in einem einzigen Zug durchlaufen und man erhält den klassischen Hamiltonkreis, (z. B. Im nächsten Bild der Teilgraph g-x). In der Regel schliessen sich aber bereits Teilkreise, bevor alle Kanten einmal durchlaufen sind. Man beginnt dann erneut an einer noch freien Ecke, bis alle Kanten einmal durchlaufen sind. Die Teilkreise haben alle eine gerade Kanten- und Eckenzahl und bilden zusammen eine Gruppe mit 3 Elementen.

Unterschiedliche Lösungen auf g liegen dann vor, wenn sie sich in mindestens einem ihrer drei Teilkreise unterscheiden. Ein bestimmter Teilkreis kann in mehreren Lösungen vorkommen. Eine Lösung λi besteht aus drei disjunkten Teilgraphen {gx,gy,gz} mit gx = Menge der Kanten der Farbe x und sinngemäss gy und gz, bestehend aus je k/3 Kanten der Farben {x,y,z}. Im Bild oben sind im unteren Teil die drei möglichen Darstellungen ohne die dritte Farbe gezeigt.

Ketten

Jeder dieser drei Teilkreise ist die äussere Begrenzung einer Flächen-Kette. Diese Ketten enthalten in ihrem Inneren keine Ecken und die umschlossenen Flächen sind abwechselnd mit zwei der vier Flächenfarben {a,b,c,d} nach dem Tetraederschema gefärbt. Sie bilden deren Skelett, perlenschnurartige Strukturen, die sowohl offen und auch verzweigt, oder ringförmig - dann aber geradzahlig - sein können. Die Kanten im Inneren dieser Teilkreise und auch zwischen ihnen haben im obigen Beispiel die Farbe z. Sie sind Stege zwischen den Flächen der Ketten, vergleichbar mit Brücken zwischen von Wasser umgebenen Landflächen in einer Geländekarte. Im Dualen Gaphen g‘, der entsteht, wenn man z.B. in der korrespondierenden Landkarte die Hauptstädte durch Autobahnen verbindet, lässt sich dieser Zusammenhang anschaulich darstellen. Die Rolle von Flächen und Ecken sind vertauscht, die Färbungen bleiben gleich.

Reduktion und Expansion

Jeder dreireguläre Graph g kann durch schrittweises Entfernen einer beliebigen Kante auf die Projektion des Tetraeders oder eine andere Grundform mit wenigen Flächen reduziert werden. Umgekehrt kann g durch Einfügen von Kanten innerhalb seiner Flächen "von Kante zu Kante" expandiert werden. Dadurch verschwinden bzw. entstehen bei jedem Schritt jeweils eine Fläche, zwei Ecken und drei Kanten: die entfernte bzw. eingefügte plus die beiden durch Teilung der Anschlusskanten entstandenen. Es gibt keine anderen Möglichkeiten, Kanten kreuzungsfrei in g einzufügen.

10.Okt.2020, Neustadt/Weinstrasse

Klaus Klose

Ein computerloser Beweis des Vierfarbensatzes

Ein computerloser Beweis des Vierfarbensatzes

Behauptung: 

Jeder ebene, mindestens zweifach zusammenhängende, dreireguläre Graph g hat Lösungen (ist flächen-4- bzw. kanten-3-färbbar).

Voraussetzungen, Definitionen:

• Die Struktur von g wird beschrieben durch den Eulerschen Polyedersatz:

        Mit k = Kantenzahl,  e = Eckenzahl und f = Flächenzahl wird:    
        k–e = f–2   →     e = 2 (f-2) und k = 3 (f-2),   →  (f-2) : e : k = 1 :2 :3  

        Die Flächenzahl f ist das Mass für die „Grösse“ eines Graphen.

• Der Zusammenhang von Flächen-4, und Kanten-3-Färbung wird durch das                 Tetraederschema beschrieben:

• Bis zu einer Flächenzahl h (Flächenhorizont) seien alle möglichen Färbungen (Lösungen) aller g bekannt bzw. leicht manuell zu finden.

• Jeder Graph g kann durch Einfügen zweier gleichgerichteter Kanten im Inneren einer Fläche ohne Verlust der Dreiregularität und Färbbarkeit expandiert werden. 

• Weitere Definitionen unter "Anmerkungen.. "

Aus der Flächengewichtsformel Σ(qn)=12 mit qn= 6-n, dem "Gewicht" der Flächen folgt, dass ein jeder dreireguläre Graph g mindestens ein Vier- oder Fünfeck enthalten muss, wenn Zwei- und Dreiecke als trivial ausgeschlossen sind. Enthält g(h+1) mindestens ein Viereck, so kann man dieses als Resultat der Einfügung eines Kantenpaares in einen Graphen auf h-1 mit sicher bekannten Lösungen verstehen. Die Teilung von Flächen durch Einziehen von Kantenpaaren kann auf vielfältige Weise in allen Flächen von g und dort an beliebiger Stelle "von Kante zu Kante" erfolgen. Alle Graphen g(h+1), die mindestens ein Viereck enthalten, kann man sich so entstanden vorstellen, und eine Lösung kann aus g(h-1) expandiert werden. Die Geradzahligkeit der Kanten auf den betreffenden Teilkreisen und deren abwechselnde Färbung bleibt erhalten. Nach der Erhöhung von h um 1 und mit der selben Argumentation ist der Induktionsschluss also auf alle g anwendbar, die mindestens ein Viereck enthalten:

•  Alle g, die mindestens ein 4-Eck enthalten, haben also eine Lösung.

Nach der Flächengewichtsformel sind 6-Ecke mit dem Gewicht=0 neutral. Um den Beweis für alle beliebigen g führen zu können, muss also jetzt noch ein Weg für Graphen gefunden werden, die ausschliesslich Fünfecke und Grössere enthalten (n-Ecke mit n<4 ausgeschlossen). Unter der Menge aller denkbaren drei-regulären Graphen stellt diese Kategorie nur eine sehr beschränkte Teilmenge dar. Der Iso-Dodekaeder ist deren kleinster Vertreter. Es gibt nur zwei mögliche Ausprägungen:

a.) Der diskusförmige konvexe Polyeder, bei dem die Fünfecke im Zickzack um zwei gegenüberliegende Stirnflächen beliebiger Grösse angeordnet sind, hat immer Lösungen. Gibt man einer Stirnfläche die Farbe a, so können die angrenzenden Fünfecke abwechselnd mit den Farben b und c gefärbt werden (blauer Pfeil) und sinngemäss für die gegenüberliegende Stirnfläche (roter Pfeil). Bei ungeradzahligen Stirnflächen können die übrigbleibenden zwei Fünfecke (schraffiert) so eingefärbt werden, dass es zu keiner Farbkollision kommt.

b.) Der kugelförmige konvexe Polyeder, bei dem die Fünfecke ringförmig um die anderen n-Ecke beliebiger Grösse mit n>4 angeordnet sind. Hier kann je ein Doppel-Fünfeck durch eine Kante ersetzt werden und umgekehrt. Die Kanten des so entstandenen, stark reduzierten Graphen werden nach den oben dargelegten Regeln 3-gefärbt. Seine Kanten werden wiederum zu Doppel-Fünfecken expandiert und diese nach dem Tetraederschema 4-gefärbt.

Ein beliebiger (kanten-3-gefärbter) Graph g kann also durch Ersetzen aller seiner Kanten durch Doppel-Fünfecke zu einem Graphen mit n ≥ 5 für alle seine n-Ecke (Flächen) expandiert werden. Für die erste Kante (im Bild die mit der Farbe z (blau) zwischen den 2 angrenzenden Flächenfarben {a;c} ) gibt es zunächst 2 Flächen-Farbkombinationen {bd;db} für das zwischen den Flächen {B, A} eingefügte Doppel-Fünfeck. Für die folgenden, A umgebenden Doppel-Fünfecke ist jeweils nur noch eine der beiden Farbkombinationen möglich. Das gilt sinngemäss für alle Flächen A...J. Nach der Flächengewichtsformel muss ein Graph mit ausschliesslich 5-Ecken und grösseren deren mindestens 12 enthalten und diese müssen ringförmig um die restlichen n-Ecke angeordnet sein. Ersetzt man in der obigen Grafik ein Doppelfünfeck, z.B. das zwischen den Flächen A und B durch eine Kante, entstehen sogleich zwei Vierecke. Es können also nur alle Kanten des ursprünglichen Graphen durch Doppelfünfecke ersetzt werden.

Wenn in obigem Beispiel die blaue Kante zwischen den Flächen A und B durch das Doppelfünfeck b/d ersetzt wird, passt für die folgenden, A umgebenden Doppel-5-Ecke jeweils eine der beiden Farbkombinationen. Das gilt sinngemäss für alle Flächen (A...J).

Daraus schliesse ich, dass es keinen ebenen, dreiregulären, mindestens zweifach zusammenhängenden Graphen ohne eine einzige Lösung geben kann.

Neustadt, 09.09.2020 

Klaus Klose

Viefarbensatz, Suchalgorithmen

Der Vierfarbensatz gilt heute als bewiesen, wenn auch nur mittels massivem Computereinsatz. Es ist aber aufwändig, und für beliebig, grosse Graphen sogar unmöglich "Lösungen", also gültige Flächen-Vierfärbungen oder gleichwertige Kanten-Dreifärbungen zu finden. Ausser dem Durchprobieren aller möglichen Kombinationen auf dem Computer ist kein Verfahren bekannt. Dazu gibt es aber verschiedene Ansätze und es gilt die effizienteste mit der geringsten Laufzeit zu finden.  Die aufwändigste wäre das Durchprobieren aller vier Flächenfarben auf f Flächen des Graphen. Das ergibt 4^f Möglichkeiten. Bei f=10 wäre das ca. 1Mio. Deutlich weniger Versuche kostet die folgende Suchmethode:

Man installiert in jeder Fläche des ungefärbten Graphen (1) einen "Wirbel", der entweder rechts- oder linksdrehend sein kann (2). Das ergibt 2^f Kombinationen. Mit f=10 ergibt sich die Zahl 1024, also deutlich weniger als im ersten Beispiel. Jede Kante erhält einen Richtungspfeil, wenn die "Strömung" der Wirbel auf beiden Seiten gleichgerichtet ist (3). Sobald an einer Ecke drei Pfeilspitzen oder Pfeilenden Zusammentreffen, wird diese Kombination verworfen. Bei den übrigbleibenden Kombinationen können nun die Richtungspfeile beginnend an einer beliebigen Stelle abwechselnd mit zwei der drei Kantenfarben (blau/grün) gefärbt (4), und schliesslich die dritte Kantenfarbe (rot) ergänzt werden. Die Suche nach den Lösungen ist also ein np-schweres Problem, der Beweis des Vierfarbensatzes aber nicht zwangsläufig!

Die Anzahl der Färbungsmöglichkeiten für die drei an einer Ecke zusammentreffenden Kanten steigt exponentiell mit 2^(e/2) bzw. 2^(F-2) mit e=Eckenzahl und f=Flächenzahl. Betrachtet man den Graphen als aus elastischen Fäden geknüpftes Netz, und durchtrennt einen beliebigen davon, so entsteht ein gerichtetes Bündel aus Fäden und Knoten, wenn man die beiden „losen Enden“ wie in nachstehender Grafik gezeigt in die Länge zieht.

Es entsteht ein bipartiter Baum, der nach Einführung von Richtungspfeilen genau gleich viele Verzweigungs- und Vereinigungsknoten enthält. In der Regel zerfallen beide in eine Anzahl kleinere Bäume, die zusammen einen bipartiten Wald bilden. Es genügt, die Färbungsmöglichkeiten an einem der beiden durchzuprobieren. Die Färbung der „anderen Hälfte“ kann schlüssig ergänzt werden. Dieses wäre also die effizienteste Methode. Auf der mein graphischer, in Visual Basic geschriebener Editor beruht, mit dessen Hilfe ich die essentiellen Erkenntnisse gewonnen habe, die schliesslich zu meinem Beweis geführt haben.