Beweis für das Vier-Farben-Theorem?

Question

ich habe mir gestern abend das Vier-Farben-Theorem angeschaut, und verstehe seitdem nicht, was daran so schwierig ist, einen klassischen Beweis zu finden, da ich glaube, es selbst bewiesen zu haben.

Mein Beweis ist wie folgt, und ich würde mich freuen, wenn mir jemand sagt, wo der Fehler liegt:

Die Aussage, dass sich die Knoten eines planaren Graphs mit vier Farben einfärben lassen, ist äquivalent zur Aussage,

dass die Anzahl der Knoten, die mit einem beliebigen anderen Knoten verbunden sind, und alle untereinander verbunden sind, höchstens 4 sein kann.(Ansonsten bräuchte man ja mehr als 4 Farben)

Spätestens, wenn man sich nun den folgenden Graphen ansieht, wird klar, dass diese Aussage wahr ist, denn ein weiterer Knoten kann nicht mit allen anderen vier Knoten verbunden sein, was spätestens bewiesen ist, wenn man sich die folgende Fallunterscheidung anschaut:

D----------------C                                                                                                                            \   \  /    /                                                                                                                                  \   A   /                                                                                                                                      \  I  /                                                                                                                                           B

1.   Ein weiterer Knoten liegt außerhalb des "Dreiecks" ABC, dann kann er nicht mit A verbunden sein, da der Graph dann nicht mehr planar wäre.

2. Der weitere Knoten liegt innerhalb von BCD, also obda im "Dreieck" ABC, dann kann er nicht mit D in Verbindung stehen.

Somit wäre meines Erachtens nach das Theorem bewiesen; bin ich jetzt schlauer als die ganzen Mathematiker, die seit Jahrhunderten versuchen, einen klassischen Beweis zu finden?

Comments

Deine Aussage formalisiert:

Sei G ein planarer Graph, dann sind äquiva.:

(i) Die chromatische Zahl von G ist höchstens 4. (Vier Farben Satz)

(ii) Für alle Knoten v gilt: ist U eine Clique (eine Teilmenge von Knoten die alle paarweise miteinander verbunden sind) die v enthält, so enthält U höchstens 4 Knoten.

(i) auf (ii) ist trival, da die chromatische Zahl immer größer als die Cliquenzahl (also die Anzahl der Knoten in der größtmöglichen Clique) ist.

Es ist aber (zumindest mir) keineswegs klar warum aus (ii) auch (i) folgen sollte. Klar kannst du jede Clique mit Größe ≤4 auch mit maximal 4 Farben färben. Aber dann weißt du ja nur was über "lokale Färbbarkeit". IMHO ist die Folgerung, dass man dann auch den ganzen Graphen mit 4 Farben einfärben kann nicht trivial.

---

 

ich habe jetzt den Beweis ausführlicher aufgeschrieben; ich hoffe das ist verständlicher.

PS:

Ich habe nicht angenommen, dass 

"Die Anzahl der Knoten, die mit einem beliebigen anderen Knoten verbunden sind, und alle untereinander verbunden sind, kann höchstens 4 sein kann.(Ansonsten bräuchte man ja mehr als 4 Farben)", 

sondern nur gesagt, dass dies äquivalent zum zu zeigenden Satz ist.

Das mit dem Graph hat wohl leider auch nicht geklappt, ich hoffe, dass das, was ich meine jetzt klarer wird.

Fehler: Dateityp „pdf“ ist nicht erlaubt.

---

sondern nur gesagt, dass dies äquivalent zum zu zeigenden Satz ist.

Und ich vermute, dass genau hier der Fehler liegt. Der VFS impliziert zwar deine Aussage wie ich oben geschrieben habe. Aber die Rückrichtung ist nicht trival.

Du zeigst ja nur, dass du jedes "Netzwerk" einzeln mit 4 Farben einfärben kannst. Aber daraus zu folgern, dass du alle Netzwerk gleichzeitig mit 4 Farben einfärben kannst, s.d. diese Färbungen alle kompatibel zueinander sind, ist wahrscheinlich der Knackpunkt.

Answer 1

In Deinem Beweis steckt ein häufig üblicher Denkfehler : in einem Beweisschritt wird die zu beweisende Aussage als gültig angenommen. In Deinem Fall genau hier :

Die Anzahl der Knoten, die mit einem beliebigen anderen Knoten verbunden sind, und alle untereinander verbunden sind, kann höchstens 4 sein kann.(Ansonsten bräuchte man ja mehr als 4 Farben).

Aber genau das gilt es zu beweisen, ausserdem ist die Anzahl der Knoten nicht auf vier beschränkt. Stell Dir eine Torte mit 12 vormarkierten Stücken vor. In der Mitte der Torte liegt ein Kreis. Alle Tortenstücke grenzen an den Kreis. Der Graph, der hier zu untersuchen ist, hat 13 Knoten.

Die Frage ist also, ob ein Graph mit N Knoten in einer Ebene 4-färbbar ist. Diese Frage ist nicht auf Graphen mit N=4 Knoten beschränkt.

Answer 2

Hallo

deinen Satz ;"Die Aussage, dass sich die Knoten eines planaren Graphs mit vier Farben einfärben lassen, ist äquivalent zur Aussage, dass die Anzahl der Knoten, die mit einem beliebigen anderen Knoten verbunden sind, und alle untereinander verbunden sind, höchstens 4 sein kann.(Ansonsten bräuchte man ja mehr als 4 Farben)

verstehe ich nicht, der Vierfarbensatz gilt für ALLE Karten, allerdings Gebiete die nur einen Punkt gemeinsam haben, müssen nicht verschieden gefärbt sein.

Was du mit "alle untereinander verbunden sind" meinst verstehe ich auch nicht, irgendwie scheinst du von einem Dreieck auszugehen, und zu sagen weitere Punkte sind nicht möglich.

Deine Zeichnung verstehe ich nicht. Was sollen die Striche sein?

wegen deine "Äquivalent" Aussage denke ich, du hast das Problem nicht oder falsch verstanden.

Gruß lul