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