Vier-Farben-Satz Beweis
Neue Frage »

04.11.2024, 12:46 kilian_p Auf diesen Beitrag antworten »
Vier-Farben-Satz Beweis
Hallo,
mir hat es der Vier-Farben-Satz angetan und ich denke, ich habe einen Ansatz für seinen Beweis (hier werden einige Leser bestimmt schon schmunzeln müssen). Zumindest kann ich keine Lücken oder Fehler in diesem Ansatz entdecken und würde mich deshalb sehr freuen, wenn das mal jemand prüfend anschaut. Ich habe nicht so sehr einen mathematischen Hintergrund (spätestens jetzt werden wohl alle schmunzeln), sondern eher einen technischen. Deshalb fokussiere ich mich auf die Konstruierbarkeit von k+1-färbbaren aus k-färbbaren Graphen, um zu zeigen, dass 5-färbbare Graphen nicht-konstruierbar sind.
Dazu habe ich mal ein kurzes Video gemacht, um die Konstruktionsschritte und deren Bedingungen an einigen Beispielgraphen zu zeigen: youtu.be/rVkHGRnH2Bo. Ich habe das ganze auch ausführlich formuliert und kann das gern hier posten.

Die grundlegenden Bedingungen sind:
  1. Der Graph muss planar sein - keine Kanten dürfen sich schneiden.
  2. Farbungleichheitsbedingung (FUB): Durch Kanten verbundene Knoten dürfen nicht die gleiche Farbe haben.
  3. Ein Graph ist k-färbbar, wenn k Farben ausreichen, seine Knoten so einzufärben, dass die FUB erfüllt ist.
  4. Die kleinstmöglichen planaren k-färbbaren Graphen für k<5 sind K_k, wobei je Farbe nur ein Knoten existiert und jeder Knoten mit jedem anderen durch eine Kante verbunden ist.

Kurz zusammengefasst sieht mein Ansatz wie folgt aus
  1. Für jeden k+1-färbbaren Graphen x mit n Knoten und k_x Kanten gibt es mindestens einen k-färbbaren Graphen y, der aus den gleichen n Knoten und k_y Kanten besteht, die eine Untermenge der k_x Kanten von x sind (k_y<k_x).
  2. Daraus folgt, dass x aus y nur durch das Hinzufügen von Kanten konstruiert werden kann.
  3. Da x k+1-färbbar ist, muss es beim Hinzufügen einer dieser Kanten zur Notwendigkeit einer weiteren Farbe kommen - diesen Schritt nenne ich Emergenz.
  4. Zur Emergenz kommt es nur, wenn durch die Kante zwei gleichfarbige Knoten verbunden werden, die nicht unabhängig voneinander umgefärbt werden können, ohne die FUB zu verletzen.
  5. Zwei gleichfarbige Knoten können genau dann nicht unabhängig voneinander umgefärbt werden, wenn sie Bestandteil eines bestimmten (Teil-) Graphen sind.
  6. Bestimmte Graphen zeichnen sich dadurch aus, dass die Mengen gleichfarbiger Knoten festgelegt sind und nur als gesamte Menge die Farbe wechseln können, ohne die FUB zu verletzen.
  7. Mithilfe der Erweiterungsregel (siehe unten) kann gezeigt werden, dass alle 4-färbbaren bestimmten Graphen maximal planar sind, ihnen also keine Kante hinzugefügt werden kann.
  8. Deshalb gibt es keinen 4-färbbaren Graphen, aus dem sich durch Hinzufügen einer Kante ein 5-färbbarer Graph konstruieren lässt.
  9. Es kann also kein 5-färbbarer Graph existieren, da er sich sonst durch das Entfernen von Kanten zu einem 4-färbbaren Graphen trivialisieren ließe, aus dem er wiederum durch das Hinzufügen von Kanten konstruierbar wäre.
  10. Erweiterungsregel: Um einem k-färbbaren bestimmten Graphen einen neuen Knoten so hinzuzufügen, dass dieser Knoten farblich bestimmt ist und damit der Graph bestimmt bleibt, sind je neuem Knoten mindestens k-1 neue Kanten nötig, unabhängig davon, ob sie sofort oder im Nachhinein durch die Verbindung mit weiteren neuen Knoten erzeugt werden.
  11. K_k sind alle bestimmt.
  12. Mithilfe beliebig vieler Schritte der Erweiterungsregel kann jeder k-färbbare bestimmte Graph aus K_k konstruiert werden.
  13. Für 4-färbbare bestimmte Graphen werden dabei aufgrund der Erweiterungsregel mit jedem neuen Knoten drei Kanten hinzugefügt, so dass die Gleichung k=3n-6 für alle 4-färbbaren bestimmten Graphen erfüllt ist und sie deshalb maximal planar sind.
04.11.2024, 17:45 Elvis Auf diesen Beitrag antworten »

Muss man nicht beweisen, wurde 1976 von Appel und Haken schon bewiesen. Falsche "Beweise" gibt es auch schon genug. Kannst du beweisen, dass dein Beweisversuch ein richtiger Beweis und kein falscher "Beweis" ist ?
04.11.2024, 17:58 kilian_p Auf diesen Beitrag antworten »

Vielen Dank für deine Antwort! So wie ich es verstanden habe, ist der Beweis von Appel und Haken ein Computerbeweis, während mein konstruktiver Ansatz methodisch-logisch ist. Computerbeweise sind aus mehreren Gründen umstritten und man ist deshalb immer bemüht, einen logisch-methodischen Beweis zu finden, weil der von Menschen direkt nachvollzogen werden kann und seine Richtigkeit eben nicht noch extra bewiesen werden muss.

Außerdem kann ich deine Argumentation nicht ganz nachvollziehen:
Wenn ein Beweis so schwer nachvollziehbar ist, dass seine Richtigkeit mit einem zweiten Beweis bewiesen werden muss, muss man dann nicht auch wieder die Richtigkeit des zweiten Beweises beweisen usw.?

Ich denke, das Ziel ist immer, einen Beweis so zu formulieren, dass er verständlich und menthal nachvollziehbar ist. Das habe ich versucht und wenn jemand eine Stelle findet, die unschlüssig oder gar falsch ist, würde ich mich über konstruktive Kritik freuen.
04.11.2024, 20:01 tobit Auf diesen Beitrag antworten »

Hallo kilian_p,

leider habe ich schlechte Erfahrungen damit gemacht, mich in die Gedankenwelt von nicht studierten Mathematikern einzudenken, die meinen, sie hätten einen bahnbrechenden Beweis erbracht. Das kann aufgrund der begrenzten Fähigkeiten der mathematischen Beweisdarstellung sehr mühsam sein und wenn man dann endlich soweit eingedrungen ist, dass man den/die entscheidenden Fehler von den behebbaren Fehlern getrennt hat, wurde mir in der Vergangenheit dafür meist nicht gedankt, sondern die Personen hielten an ihrem "Beweis" fest, so dass die ganze Mühe sich umsonst anfühlte. Daher möchte ich nicht versprechen, hier entsprechenden Aufwand zu betreiben.


Erste Anmerkungen meinerseits ohne Anspruch darauf, bereits den Kern der Problematik erfasst zu haben:

Schon bei 1. bin ich nicht sicher, ob das einfach begründbar oder möglicherweise gar falsch ist.

Spätestens 4. und 5. sind dann für mich nicht mehr prüfbar, weil undefinierte Begriffe wie "unabhängig voneinander umfärben" und "Bestimmte Graphen" vorkommen. Falls 6. die Definition eines "bestimmten Graphen" sein soll, ist das für mich nicht sehr erhellend: Dort taucht dann der undefinierte Begriff "als gesamte Menge die Farbe wechseln" auf.

Bei der Folgerung 8. aus 7. scheint das entscheidende Wörtchen "bestimmten" (was auch immer das genau heißen mag) verloren gegangen zu sein. Aus der schwächeren Aussage
"Deshalb gibt es keinen 4-färbbaren BESTIMMTEN Graphen, aus dem sich durch Hinzufügen einer Kante ein 5-färbbarer Graph konstruieren lässt." (*)
wird so stillschweigend unter 8. genannte Aussage gemacht.
Hast du ein Argument dafür, dass (*) bereits deine Aussage 8. impliziert?


Viele Grüße
Tobias
05.11.2024, 08:13 Elvis Auf diesen Beitrag antworten »

Ein Beweis muss so formuliert und aufgeschrieben werden, dass man ihn nachvollziehen und verstehen kann. Dein "Beweis" ist völlig unverständlich, ich persönlich halte ihn für Geschwafel - bis ein Beweis vorliegt.
05.11.2024, 19:34 kilian_p Auf diesen Beitrag antworten »

Hallo tobit,
vielen Dank für deine kurzfristige Antwort!

Zitat:
Original von tobit
leider habe ich schlechte Erfahrungen damit gemacht, mich in die Gedankenwelt von nicht studierten Mathematikern einzudenken, die meinen, sie hätten einen bahnbrechenden Beweis erbracht. Das kann aufgrund der begrenzten Fähigkeiten der mathematischen Beweisdarstellung sehr mühsam sein und wenn man dann endlich soweit eingedrungen ist, dass man den/die entscheidenden Fehler von den behebbaren Fehlern getrennt hat, wurde mir in der Vergangenheit dafür meist nicht gedankt, sondern die Personen hielten an ihrem "Beweis" fest, so dass die ganze Mühe sich umsonst anfühlte. Daher möchte ich nicht versprechen, hier entsprechenden Aufwand zu betreiben.


Das klingt nachvollziehbar. Schön, dass du dir meinen Ansatz trotzdem durchgelesen hast. Dass man hier nicht viel Aufwand beim Durchlesen betreiben muss, war auch der Grund, weshalb ich meinen Ansatz nur kurz umrissen habe. Darunter leiden natürlich Verständlichkeit und Schlüssigkeit. Deshalb habe ich jetzt mal den Volltext als Datei angehängt und dort die Sätze auch durchnummeriert, damit man einfacher darauf Bezug nehmen kann. Ich bin mir bewusst, dass ich der für Beweise üblichen Sprache nicht mächtig bin (und versuche das mit algorithmischem Denken auszugleichen ;-)). Das war für mich auch der Grund, das Video zu machen, da schlechte Formulierungen vielleicht weniger zu Missverständnissen führen, wenn man direkt am Graphen sieht, was gemeint ist. Das Video dauert 12min - Zum Durchlesen des angehängten Pdfs braucht man wahrscheinlich ähnlich lang.
Nun will ich aber auf deine Anmerkungen eingehen:

Zitat:

Erste Anmerkungen meinerseits ohne Anspruch darauf, bereits den Kern der Problematik erfasst zu haben:

Schon bei 1. bin ich nicht sicher, ob das einfach begründbar oder möglicherweise gar falsch ist.


Unter 1. habe ich versucht folgendes zusammenzufassen (siehe Video bei 2:52):
Aus jedem k-färbbaren Graphen, der Kanten enthält, kann eine Kante entfernt werden.
Führt man diesen Schritt oft genug durch, wird der so entstehende Graph k-1 - färbbar.
Beispiel: entferne ich aus dem 4-färbbaren K_4 eine Kante, ist der entstehende Graph 3-färbbar. Je nachdem welche Kanten ich danach entferne, entsteht nach dem 2.,3. oder 4. Schritt ein 2-färbbarer Graph. Nach dem 6. Schritt habe ich die letzte Kante entfernt und der Graph besteht nur noch aus Knoten - ist also 1-färbbar (“Lose” Knoten und Teilgraphen lasse ich in meinem Ansatz zu, weil sie im geographischen Ausgangsthema ja Inselstaaten bzw. -staatengruppen entsprechen können, die keine (Land-) Grenze zu anderen Staaten haben).
Das Entfernen dieser Kanten ist umkehrbar. Da sich jeder Graph also durch Entfernen von Kanten in einen Graphen geringerer Farbigkeit überführen lässt, so lässt er sich auch aus ihm durch das Hinzufügen von Kanten konstruieren. Wobei es eben bei der Hinzufügung einer der Kanten zur Emergenz einer weiteren Farbe kommen muss.

Zitat:
Spätestens 4. und 5. sind dann für mich nicht mehr prüfbar, weil undefinierte Begriffe wie "unabhängig voneinander umfärben" und "Bestimmte Graphen" vorkommen. Falls 6. die Definition eines "bestimmten Graphen" sein soll, ist das für mich nicht sehr erhellend: Dort taucht dann der undefinierte Begriff "als gesamte Menge die Farbe wechseln" auf.


Hier muss ich etwas weiter ausholen, das steht aber auch im angehängten Pdf. Die Eigenschaften “unterbestimmt”, “bestimmt” und “überbestimmt” beziehen sich auf das Ungleichungssystem, das durch die FUB (Farbungleichheitsbedingung verbundener Knoten) und die Kanten eines Graphen erzeugt wird - darin steht je Kante eine Ungleichung der durch sie verbundenen Knoten (z.B. 4:28 im Video). Existiert genau eine Lösung für das Ungleichungssystem, ist es (und der dazugehörige Graph) “bestimmt”, existieren mehrere Lösungen, ist es “unterbestimmt” und gibt es keine Lösung, ist es “überbestimmt” (analog zu Gleichungssystemen).
Bei der Einfärbung der Knoten gemäß FUB werden die n Knoten eines k-färbbaren Graphen ja zu k Gruppen gleicher Farbe (Knotenmengen) aufgeteilt.
Dass ein k-färbbarer bestimmter Graph nur eine mögliche Lösung hat, bedeutet, es existiert nur eine Möglichkeit für die Aufteilung der n Knoten auf die k Knotenmengen, um die FUB zu erfüllen. Dann lassen sich eben keine Knoten mehr “unabhängig voneinander umfärben” (das war wirklich schlecht formuliert, sorry)

Zitat:
Bei der Folgerung 8. aus 7. scheint das entscheidende Wörtchen "bestimmten" (was auch immer das genau heißen mag) verloren gegangen zu sein. Aus der schwächeren Aussage
"Deshalb gibt es keinen 4-färbbaren BESTIMMTEN Graphen, aus dem sich durch Hinzufügen einer Kante ein 5-färbbarer Graph konstruieren lässt." (*)
wird so stillschweigend unter 8. genannte Aussage gemacht.
Hast du ein Argument dafür, dass (*) bereits deine Aussage 8. impliziert?


Ich will zeigen, dass Emergenz nur in Graphen mit “bestimmtem” Ungleichungssystem möglich ist. Diese können Teilgraphen eines größeren unterbestimmten Graphen sein. Enthält ein unterbestimmter Graph aber keinen “bestimmten”, so ist auch keine Emergenz möglich.
Ich hoffe, das war jetzt etwas verständlicher.
Gruß
Kilian
 Anzeige 
 
05.11.2024, 22:48 Elvis Auf diesen Beitrag antworten »

Bist du sicher, dass du nicht bewiesen hast, dass man für nichttriviale Karten mindestens 4 Farben braucht?
05.11.2024, 23:14 HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Bist du sicher, dass du nicht bewiesen hast, dass man für nichttriviale Karten mindestens 4 Farben braucht?

Na das kann man aber auch einfacher haben. Big Laugh

[attach]57981[/attach]
06.11.2024, 07:51 zweiundvierzig Auf diesen Beitrag antworten »

Zitat:
Original von kilian_p
Computerbeweise sind aus mehreren Gründen umstritten

Die ursprünglich simulationsgestützten Beweise wurden später formal verifiziert, von Gonthier—Werner (2005) im Beweisassistenten Rocq (ehemals: Coq).
06.11.2024, 08:17 tobit Auf diesen Beitrag antworten »

Zitat:
Unter 1. habe ich versucht folgendes zusammenzufassen (siehe Video bei 2:52):
Aus jedem k-färbbaren Graphen, der Kanten enthält, kann eine Kante entfernt werden.
Führt man diesen Schritt oft genug durch, wird der so entstehende Graph k-1 - färbbar.
Beispiel: entferne ich aus dem 4-färbbaren K_4 eine Kante, ist der entstehende Graph 3-färbbar. Je nachdem welche Kanten ich danach entferne, entsteht nach dem 2.,3. oder 4. Schritt ein 2-färbbarer Graph. Nach dem 6. Schritt habe ich die letzte Kante entfernt und der Graph besteht nur noch aus Knoten - ist also 1-färbbar (“Lose” Knoten und Teilgraphen lasse ich in meinem Ansatz zu, weil sie im geographischen Ausgangsthema ja Inselstaaten bzw. -staatengruppen entsprechen können, die keine (Land-) Grenze zu anderen Staaten haben).

Die Betrachtung von Beispielen ersetzt keinen allgemeinen Beweis.
(Warum soll ein k-färbbarer Graph beim Entfernen einer Kante nicht z.B. k-2-färbbar werden?)

Zitat:

Zitat:
Bei der Folgerung 8. aus 7. scheint das entscheidende Wörtchen "bestimmten" (was auch immer das genau heißen mag) verloren gegangen zu sein. Aus der schwächeren Aussage
"Deshalb gibt es keinen 4-färbbaren BESTIMMTEN Graphen, aus dem sich durch Hinzufügen einer Kante ein 5-färbbarer Graph konstruieren lässt." (*)
wird so stillschweigend unter 8. genannte Aussage gemacht.
Hast du ein Argument dafür, dass (*) bereits deine Aussage 8. impliziert?


Ich will zeigen, dass Emergenz nur in Graphen mit “bestimmtem” Ungleichungssystem möglich ist. Diese können Teilgraphen eines größeren unterbestimmten Graphen sein. Enthält ein unterbestimmter Graph aber keinen “bestimmten”, so ist auch keine Emergenz möglich.
Ich hoffe, das war jetzt etwas verständlicher.

Deine Aussage
"Enthält ein unterbestimmter Graph aber keinen “bestimmten”, so ist auch keine Emergenz möglich." (**)
wäre ggf. zu beweisen.
Selbst wenn dieser Beweis gelingt, sehe ich nicht, wie daraus 8. folgen soll.
(Bei (**) geht es offenbar um ein "Enthaltensein" im Sinne von "Variieren von Knoten und Kanten", bei 8. jedoch nur um das "Variieren von Kanten bei festgehaltener Knotenmenge".)

Im PDF sehe ich analog das gleiche Problem bei der "Schlussfolgerung" von 16.4 nach 16.5.
06.11.2024, 11:27 kilian_p Auf diesen Beitrag antworten »

Zitat:
Original von tobit
Die Betrachtung von Beispielen ersetzt keinen allgemeinen Beweis.
(Warum soll ein k-färbbarer Graph beim Entfernen einer Kante nicht z.B. k-2-färbbar werden?)

Du hast recht. Die Stelle werde ich mir mal genauer ansehen.

Zitat:

Deine Aussage
"Enthält ein unterbestimmter Graph aber keinen “bestimmten”, so ist auch keine Emergenz möglich." (**)
wäre ggf. zu beweisen.
Selbst wenn dieser Beweis gelingt, sehe ich nicht, wie daraus 8. folgen soll.
(Bei (**) geht es offenbar um ein "Enthaltensein" im Sinne von "Variieren von Knoten und Kanten", bei 8. jedoch nur um das "Variieren von Kanten bei festgehaltener Knotenmenge".)

Im PDF sehe ich analog das gleiche Problem bei der "Schlussfolgerung" von 16.4 nach 16.5.

Ja, diese Stelle ist noch etwas schwach, da beschäftige ich mich auch nochmal mit.
Aber schonmal vielen Dank, dass du dir das PDF durchgelesen hast und für das konstruktive Feedback.

Gruß Kilian
06.11.2024, 17:56 tobit Auf diesen Beitrag antworten »

Hallo Kilian,

wie ich jetzt gesehen habe, lässt sich 1. mit folgender Idee zeigen:

(i) Fügt man einem l-färbbaren Graphen V eine Kante k hinzu, so gibt es eine Färbung des entstehenden neuen Graphen V' mit l+1 Farben (ich spreche hier kurz von einer l+1-Färbung).
(Beweisidee zum Nachweis von (i): Ausgehend von einer Färbung f des Ursprungsgraphen V ändert man lediglich die Färbung einen der beiden Knoten von k in eine in f noch nicht vertretene Farbe ab, um eine l+1-Färbung von V' zu konstruieren.)

(ii) Entfernt man aus einem k-färbbaren Graph W eine Kante k, entsteht ein k-färbbarer oder ein k-1-färbbarer Graph W'.
(Jede k-Färbung von W ist auch eine k-Färbung von W', also ist W' l-färbbar für ein . Wäre nun , so wäre W nach (i) mit Farben färbbar, was wegen im Widerspruch zur k-Färbbarkeit von W steht.)


Konzentriere dich also gerne auf meinen anderen Einwand.

Viele Grüße
Tobias
07.11.2024, 19:23 kilian_p Auf diesen Beitrag antworten »

Ja, genau: das mit der Umkehrung der maximalen Zunahme um eine Farbe bei der Erzeugung einer Kante zu begründen hatte ich auch vor. So gründlich wie du hätte ich es jedoch nicht formulieren können ;-)
Ich melde mich wieder, wenn ich bei dem anderen Punkt weiter bin.
Gruß Kilian
08.11.2024, 10:02 kilian_p Auf diesen Beitrag antworten »

Hier will ich nun die Punkte 4., 5. und 6. als Voraussetzung für 8. etwas detailierte begründen. Auf die für 8. auch notwendige Erweiterungsregel in 7. würde ich dann später eingehen.
Ich wähle hier erstmal den Weg der ausführlichen Beschreibung - Teile davon sind auch schon im PDF enthalten. Wenn das am Ende schlüssig wirkt, würde ich versuchen, es mathematischer zu formulieren und dann das PDF überarbeiten:

A. Was ist eine Knotenmenge M?
  1. Jeder f-färbbare Graph X mit n Knoten hat f Knotenmengen M_1,…,f.
  2. Jedes M ist einer Farbe zugeordnet. Welcher Farbe M zugeordnet ist, ist egal. Wichtig ist nur, dass sich die Farbe jedes M von den Farben der anderen Knotenmengen unterscheidet.
  3. Jedes M enthält alle Knoten einer Farbe. Knoten, die sich in derselben Knotenmenge M befinden, sind also gleichfarbig.

B. Was ist ein Ungleichungssystem?
  1. Jede Kante k_i in einem Graphen erzeugt aufgrund der FUB eine Ungleichung u_i bezüglich der Farben der beiden verbundenen Knoten.
  2. Die Menge aller durch die Kanten k_1,...,k eines Graphen erzeugten Ungleichungen u_1,...,k wird Ungleichungssystem U genannt.

C. Was ist eine Lösung für das Ungleichungssystem U?
  1. Die Aufteilung aller n Knoten auf f Knotenmengen bei Erfüllung der FUB entspricht einer Lösung für das Ungleichungssystem U von X.
  2. Existieren unterschiedliche Möglichkeiten, die n Knoten auf f Knotenmengen aufzuteilen, dann entspricht das mehreren Lösungen für U.
  3. Ist keine Aufteilung der n Knoten auf f Knotenmengen möglich, ohne die FUB zu verletzen, gibt es keine Lösung für U.

D. Was ist die Bestimmtheit eines Graphen?
  1. Analog zur Bestimmtheit von Gleichungssystemen erfolgt eine Attributierung des Ungleichungssystems U und des zugehörigen Graphen X:
  2. Hat U nur eine Lösung, ist es (eindeutig) bestimmt und X heißt bestimmt.
  3. Hat U mehrere Lösungen, ist es und damit auch X unterbestimmt.
  4. Hat U keine Lösung, ist es und damit X überbestimmt.

E. Was ist ein Teilgraph? Jede Knoten-und-Kanten-Untermenge Y des Graphen X ist ein Teilgraph von X, wobei auch Y nur inzidente Knoten und Kanten enthalten darf.

F. Bestimmtheit von Teilgraphen
  1. Da auch jedem Teilgraph anhand seiner Kanten ein Ungleichungssystem zugeordnet werden kann, gelten obige Regeln der Bestimmtheit auch für Teilgraphen.
  2. Ein Graph X kann bestimmte und/oder unterbestimmte Teilgraphen enthalten - unabhängig davon, ob X selbst bestimmt oder unterbestimmt ist.
  3. Ein f-färbbarer unterbestimmter Graph X kann aber auch keinen bestimmten Teilgraphen der Färbung f enthalten.
    (Würden hier für einen Beweis Beispiele ausreichen?)

G. Konsequenz der Graphen-Bestimmtheit für die Umfärbung von Knoten bei Erfüllung der FUB:
  1. In einem bestimmten Graphen lässt sich kein Knoten umfärben - also einer anderen Knotenmenge M zuweisen -, da nur eine Lösung existiert.
  2. In einem unterbestimmten Graphen lassen sich einer oder mehrere Knoten umfärben, ohne die FUB zu verletzen, da ja mehrere Lösungen für U existieren.
  3. Von zwei gleichfarbigen Knoten eines k-färbbaren Graphen X lässt sich deshalb nur dann keiner bei Erfüllung der FUB umfärben, wenn beide Knoten Bestandteil eines bestimmten Teilgraphen von X sind.

H. Emergenz:
  1. Werden in einem k-färbbaren Graphen X durch eine neue Kante k_i zwei gleichfarbige Knoten verbunden, von denen einer aufgrund der Unterbestimmtheit von X umgefärbt werden kann, kann die dabei entstehende Ungleichung u_i und damit U gelöst werden.
  2. Werden in einem k-färbbaren Graphen X durch eine neue Kante k_i zwei gleichfarbige Knoten verbunden, von denen keiner umgefärbt werden kann, wird zur Erfüllung der dabei entstehenden Ungleichung u_i eine zusätzliche Farbe nötig. Dieses Ereignis nenne ich Emergenz. Der so entstehende Graph Y ist also k+1-färbbar.
  3. Aus der Konsequenz der Graphen-Bestimmtheit für die Umfärbung von Knoten ergibt sich, dass Emergenz nur in bestimmten Teilgraphen auftritt.
  4. Deshalb genügt es, nachzuweisen, dass Emergenz in 4-färbbaren bestimmten Graphen nicht möglich ist, um nachzuweisen, dass Emergenz in allen 4-färbbaren Graphen nicht möglich ist.


Ich hoffe, das ist soweit verständlich formuliert. Für mich ist das schlüssig, aber das hat ja nicht viel zu bedeuten ;-)
Ich freue mich auf Antwort
Gruß Kilian
08.11.2024, 19:03 tobit Auf diesen Beitrag antworten »

Hallo Kilian,

in G. c. heißt es:
Zitat:
Von zwei gleichfarbigen Knoten eines k-färbbaren Graphen X lässt sich deshalb nur dann keiner bei Erfüllung der FUB umfärben, wenn beide Knoten Bestandteil eines bestimmten Teilgraphen von X sind.

Du nutzt später in H. d. offenbar eine stärkere Aussage:

(****) Von zwei gleichfarbigen Knoten eines k-färbbaren Graphen X lässt sich nur dann keiner bei Erfüllung der FUB umfärben, wenn beide Knoten Bestandteil eines bestimmten k-färbbaren Teilgraphen von X sind.

Nun fehlt ein Nachweis für die Vermutung (****). Ob ein solcher Nachweis gelingen kann, weiß ich nicht.

Wir müssen also wohl gegeben einen k-färbbaren Graphen X und je zwei Knoten v, w von X für die f(v)=f(w) für jede k-Färbung f von X gilt, eine Möglichkeit finden, wie wir einen bestimmten k-färbbaren Teilgraphen X' von X konstruieren, so dass X' die Knoten v und w enthält.


Ich bin inzwischen übrigens so weit, dass ich deine Gesamtidee zu verstehen meine und sie mir nicht völlig absurd erscheint. Die spannende Frage ist nun, ob jemand in der Lage ist, die in die Gesamtidee eingehende(n) Vermutung(en) zu beweisen (oder auch ob sie möglicherweise falsch sind).

Noch genauer anschauen möchte ich mir die Herleitung von 16.4 aus deinem PDF. Hier brauche ich etwas Graphentheorie-Hintergrund, den ich hoffe mir anlesen zu können.

Viele Grüße
Tobias
09.11.2024, 07:15 tobit Auf diesen Beitrag antworten »

Nach näherem Anschauen von 16.4 erscheint auch hier die Beweisidee unter Nutzung von Graphentheorie-Wissen nicht absurd.
(Hier müsste es wohl heißen: "Daraus folgt, dass jeder 4-färbbare PLANARE bestimmte Graph maximal planar ist.")

Unklar ist mir jedoch, wie sich ggf. die für die Beweisidee benötigten Aussagen 16.2/16.3 beweisen lassen.

16.2 folgt zwar aus 15.1, aber 15.1 kann ich ebenfalls nicht beweisen.
09.11.2024, 09:49 tobit Auf diesen Beitrag antworten »

Die beim Beweis von 16.4 eingehende Vermutung "Für jeden bestimmten 4-färbbaren Graphen mit genau n Knoten und genau k Kanten gilt k=3n-6" ist übrigens falsch.

Gegenbeispiel:
Betrachte den Graph mit Knoten 0,1,...,5 und folgenden Kanten:
Kante von 0 nach 1
Kante von 0 nach 2
Kante von 0 nach 3
Kante von 0 nach 4
Kante von 0 nach 5
Kante von 1 nach 2
Kante von 1 nach 3
Kante von 1 nach 4
Kante von 1 nach 5
Kante von 2 nach 4
Kante von 2 nach 5
Kante von 3 nach 4
Kante von 3 nach 5
Dieser Graph ist 4-färbbar, bestimmt, hat genau n=6 Knoten und k=13 Kanten, erfüllt also NICHT die vermutete Gleichung k=3n-6.

Die einzige Möglichkeit, den Beweis von 16.4 zu retten sehe ich darin, wenn es gelänge, die Vermutung für den Spezialfall planarer Graphen zu zeigen (falls sie denn in diesem Spezialfall zutrifft).
10.11.2024, 10:03 tobit Auf diesen Beitrag antworten »

Ich fasse den derzeitigen Stand meiner Analysen zusammen.

Wir haben zwei noch unbewiesene Vermutungen:

Vermutung 1:
Sei V ein 4-färbbarer Graph und v und w Knoten in V mit der Eigenschaft f(v)=f(w) für jede 4-Färbung f von V. Dann exisitert ein Teilgraph V' von V mit den Eigenschaften:
a) Die Knoten v und w sind in V' enthalten
b) V' ist 4-färbbar (d.h. nicht mit maximal 3 Farben färbbar)
c) V' ist bestimmt

Vermutung 2:
Für jeden bestimmten 4-färbbaren planaren Graphen mit genau n Knoten und genau k Kanten gilt: k=3n-6.

Wenn ich nichts übersehe, können wir aus der angenommenen Gültigkeit von Vermutung 1 und Vermutung 2 mit Kilians Ideen korrekt den Vierfarbensatz schlussfolgern. Ob ich etwas übersehen habe, würde ich prüfen, wenn ein Beweis der beiden Vermutungen vorliegt.
11.11.2024, 16:36 kilian_p Auf diesen Beitrag antworten »

Hallo Tobias,
schön, dass du dir (wieder) die Zeit genommen hast, dich mit meinen Argumentationen zu beschäftigen und sie nun nicht mehr “so absurd” erscheinen ;-).

Zitat:
Original von tobit
Hier müsste es wohl heißen: "Daraus folgt, dass jeder 4-färbbare PLANARE bestimmte Graph maximal planar ist.”


Ja, neben der Farbungleichheitsbedingung verbundener Knoten (FUB) ist Planarität eine Bedingung, die sich direkt aus dem Vier-Farben-Problem ergibt.
Ohne diese ist für jedes f>1 ein vollständiger Graph mit f Knoten f-färbbar. FUB und Planarität habe ich deshalb in meiner Argumentation oft nicht mehr explizit angeführt, weil sie für den Beweis grundlegend sind.
Anhand der Gleichung für maximal planare Graphen gilt für jeden planaren Graphen also die Ungleichung k<=3n-6.

Nun möchte ich auf folgendes eingehen:
Zitat:
Vermutung 2:
Für jeden bestimmten 4-färbbaren planaren Graphen mit genau n Knoten und genau k Kanten gilt: k=3n-6.


Für jedes f mit 0<f<5 existiert ein kleinst-möglicher f-färbbarer planarer bestimmter Graph - K_f bzw. Basiselement genannt - mit Knotenanzahl n_K und Kantenanzahl k_K:
K_1: n_K=1; k_K=0
K_2: n_K=2; k_K=1
K_3: n_K=3; k_K=3
K_4: n_K=4; k_K=6

Allgemein gilt: Möchte ich einen Knoten u zu K_f hinzufügen und dabei die Bestimmtheit des Graphen beibehalten, müssen Kanten hinzugefügt werden, damit u nur eine Farbe annehmen kann. Ansonsten gäbe es mehrere Lösungen für das Ungleichungssystem, was gleichbedeutend mit der Unterbestimmtheit des Graphen ist.

Damit u auf eine der f Farben festgelegt wird, müssen f-1 Farben für u ausgeschlossen werden. Dazu sind (mindestens) f-1 Ungleichungen, die u enthalten und somit auch (mindestens) f-1 neue Kanten nötig (“mindestens” setze ich hier in Klammern, weil ja auch mehr Kanten hinzugefügt werden könnten, aber nicht nötig sind).

Jeder bestimmte f-färbbare Graph x mit n=k+1 lässt sich deshalb konstruieren durch Hinzufügen eines Knoten u und mindestens f-1 Kanten zu K_f. Für einen weiteren neuen Knoten v gelten die gleichen Bedingungen, sodass ein Graph y mit n=k+2 sich mit dem Knoten v und f-1 Kanten aus x konstruieren lässt.

Das lässt sich (meiner Meinung nach) verallgemeinern zu: Jeder f-färbbare bestimmte Graph lässt sich aus K_f mit n_n neuen Knoten und mindestens (f-1)*n_n neuen Kanten konstruieren.
Daraus ergeben sich folgende Bedingungen für bestimmte Graphen:
n=n_K+n_n; k>=k_K+(f-1)*n_n

f=1:
n=0+n_n; k>=0+0*n_n; (trivial, weil f-1=0 und deshalb nie Kanten hinzugefügt werden);

f=2:
n=2+n_n; k>=1+1*n_n; daraus folgt: k>=n-1

f=3:
n=3+n_n; k>=3+2*n_n; daraus folgt: k>=2n-3

f=4:
n=4+n_n; k>=6+3*n_n; daraus folgt: k>=3n-6

Ein 4-färbbarer bestimmter Graph muss also die Ungleichung k>=3n-6 erfüllen, aber aufgrund der geforderten Planarität auch die Ungleichung k<=3n-6 erfüllen.
Daraus folgt: alle 4-färbbaren bestimmten Graphen sind maximal planar.
11.11.2024, 18:39 tobit Auf diesen Beitrag antworten »

Hallo Kilian,

danke für deine Rückmeldung.


Ich sehe nicht, wie man aus deinen Ideen einen Beweis für Vermutung 2 erhalten kann.

Bewiesen hast du:

Für jeden "auf gewisse Weise konstruierbaren" (das könnte man formal definieren, was damit genau gemeint ist) bestimmten 4-färbbaren planaren Graphen mit genau n Knoten und genau k Kanten gilt k=3n-6-

Vermutung 2 sagt jedoch JEDER bestimmte 4-färbbare planare Graph mit genau n Knoten und genau k Kanten erfüllt k=3n-6.

Ich sehe nicht, wie man zeigen können sollte, dass jeder bestimmte 4-färbbare planare Graph durch dein Konstruktionsverfahren entsteht.
Warum soll es nicht einen bestimmten 4-färbbaren planaren Graph mit z.B. 1000 Knoten geben, der eben nicht durch deine Konstruktion entsteht?

Wenn es gelänge, aus einem beliebigen bestimmten 4-färbbaren planaren Graphen mit mehr als 4 Knoten einen Knoten mit seinen Kanten zu entfernen und dabei die 4-Färbbarkeit und die Bestimmtheit zu erhalten, sähe dies anders aus. Dann könnte man vollständige Induktion nach der Anzahl der Knoten durchführen wie von dir angedeutet.

Konkret unbegründet ist beispielsweise deine Schlussfolgerung:
"Jeder bestimmte f-färbbare Graph x mit n=k+1 lässt sich deshalb konstruieren durch Hinzufügen eines Knoten u und mindestens f-1 Kanten zu K_f."
Gezeigt hast du nur: Jeder bestimmte f-färbbare Graph x mit n=f+1, der aus einem K_f mit einem hinzugefügten Knoten und Kanten des neuen Knotens entsteht, hat mindestens f-1 Kanten des neuen Knotens zum K_f.


Viele Grüße
Tobias
13.11.2024, 10:13 kilian_p Auf diesen Beitrag antworten »

Ja, du hast Recht. Ich glaube, die maximale Planarität aller 4-färbbaren bestimmten Graphen (und dass sie mindestens ein K_4 enthalten müssen) ergibt sich aus deren Bestimmtheit und das versuche ich mit dem konstruktiven Ansatz zu zeigen. Stattdessen zeige ich es nur für eben diesen konstruktiven Ansatz.
Ich habe dazu jetzt mal etwas recherchiert und finde vieles, was damit in Zusammenhang steht (Partition, Farbklassen, chromatische Zahl, optimale Färbung, Cliquen, perfekter Graph usw.), aber so gut wie nichts zur Bestimmtheit von Graphen außer in ein oder zwei Quellen etwas wie: “Ein Graph heißt eindeutig färbbar, wenn jede optimale Färbung zu denselben Farbklassen führt.” (algebra.uni-linz.ac.at/Students/Win/fg07s/lec/color.pdf)
Ich frage jetzt mal einen befreundeten Mathematiker, der was von Graphentheorie versteht - vielleicht ergibt sich da etwas - kann sein, dass deshalb zu meinem nächsten Post einige Tage vergehen.

Zitat:
Original von tobit
Wenn es gelänge, aus einem beliebigen bestimmten 4-färbbaren planaren Graphen mit mehr als 4 Knoten einen Knoten mit seinen Kanten zu entfernen und dabei die 4-Färbbarkeit und die Bestimmtheit zu erhalten, sähe dies anders aus. Dann könnte man vollständige Induktion nach der Anzahl der Knoten durchführen wie von dir angedeutet.
Das war meine ursprüngliche Idee - ist im Video auch noch unter dem Thema “Reduzierbarkeit” drin. Werd ich mir auch nochmal genauer anschauen.

Zitat:
Vermutung 1:
Sei V ein 4-färbbarer Graph und v und w Knoten in V mit der Eigenschaft f(v)=f(w) für jede 4-Färbung f von V. Dann exisitert ein Teilgraph V' von V mit den Eigenschaften:
a) Die Knoten v und w sind in V' enthalten
b) V' ist 4-färbbar (d.h. nicht mit maximal 3 Farben färbbar)
c) V' ist bestimmt
Ergibt sich der Beweis hier nicht aus der Gegenformulierung?
V sei ein f-färbbarer Graph und v und w Knoten in V mit der Eigenschaft f(v)=f(w). Existiert eine alternative optimale f-Färbung von V in der f(v)/=f(w), dann existiert kein bestimmter Teilgraph V’ von V, der die Knoten v und w enthält. Denn die zwei Färbungen von v und w (f(v)=f(w) und f(v)/=f(w)) bedingen zwei mögliche f-Färbungen für jeden Teilgraphen von V, der v und w enthält, - was der Definition bestimmter Graphen widerspricht.

Gruß Kilian
13.11.2024, 19:09 tobit Auf diesen Beitrag antworten »

Hallo Kilian,


so ein einsichtiges Gegenüber hatte ich in der Vergangenheit noch nicht. Also großen Respekt an dich dafür! Freude


Die eindeutige Färbbarkeit aus der von dir genannten Quelle ist ja offenbar ziemlich genau der von dir "Bestimmtheit" genannte Begriff.

Einen Graphentheoretiker zu fragen, ob er eine der beiden Vermutungen beweisen oder widerlegen kann, ist sicherlich nicht verkehrt. Mir ist dies nicht gelungen. Auch den Brute-Force-Ansatz, mit Computerhilfe viele Graphen durchzuprobieren konnte ich nur bis zu allen Graphen (bis auf Isomorphie) der Knotenzahl kleiner gleich 7 durchführen, weil ich darüber hinaus in Zeit- und Speicherplatz-Engpässe komme. Immerhin: Wenn mir dabei kein Fehler unterlaufen ist, stimmen die beiden Vermutungen für den Spezialfall von Graphen mit bis zu 7 Knoten. Das sagt natürlich aus meiner Sicht noch wenig darüber aus, ob die allgemeinen Vermutungen plausibel oder unplausibel sind.


Zu Vermutung 1 möchte ich zur Verdeutlichung gegeben einen 4-färbbaren Graphen V und Knoten v und w in V zwei Bezeichnungen für Aussagen einführen:
Sei A(V) die Aussage "es gilt f(v)=f(w) für jede 4-Färbung f von V".
Sei B(V) die Aussage "es existiert ein Teilgraph V' von V mit den Eigenschaften a), b) und c)".
Vermutung 1 sagt aus, dass in obiger Situation stets aus Aussage A(V) die Aussage B(V) folgt.

Du argumentierst nun im letzten Beitrag, dass aus der Aussage "nicht A(V)" in Kombination mit der Existenz einer 4-Färbung g von V mit g(v)=g(w) die Aussage "nicht B(V)" folgt (was korrekt ist).
Aber selbst, wenn aus "nicht A(V)" allein "nicht B(V)" folgen würde, hieße dies noch lange nicht, dass aus A(V) bereits B(V) folgt. (Aus A(V) würde hingegen in der Tat B(V) folgen, wenn aus "nicht B(V)" die Aussage "nicht A(V)" folgen würde.)

Ich sehe also keinen Ansatz für einen Beweis von Vermutung 1.


Nichtsdestotrotz: Herzlichen Glückwunsch zu deinem Erkenntnisgewinn! smile


Viele Grüße
Tobias
15.11.2024, 14:21 kilian_p Auf diesen Beitrag antworten »

Hallo Tobias,

Zitat:
Original von tobit
so ein einsichtiges Gegenüber hatte ich in der Vergangenheit noch nicht. Also großen Respekt an dich dafür! Freude
Vielen Dank - du machst es mir mit deinem geduldigen und verständlichen Stil aber auch leicht!

Zitat:
Auch den Brute-Force-Ansatz, mit Computerhilfe viele Graphen durchzuprobieren konnte ich nur bis zu allen Graphen (bis auf Isomorphie) der Knotenzahl kleiner gleich 7 durchführen, weil ich darüber hinaus in Zeit- und Speicherplatz-Engpässe komme. Immerhin: Wenn mir dabei kein Fehler unterlaufen ist, stimmen die beiden Vermutungen für den Spezialfall von Graphen mit bis zu 7 Knoten.
…das klingt spannend. Gibt es dafür öffentlich verfügbaren Code oder benutzt du eine bestimmte Software? Ich würde mir das gern mal anschauen. Erstaunlich, dass schon 7 Knoten zu Performanceproblemen führen!

Zitat:
Aber selbst, wenn aus "nicht A(V)" allein "nicht B(V)" folgen würde, hieße dies noch lange nicht, dass aus A(V) bereits B(V) folgt. (Aus A(V) würde hingegen in der Tat B(V) folgen, wenn aus "nicht B(V)" die Aussage "nicht A(V)" folgen würde.)
Ich glaub, jetzt hab ichs verstanden:
Ich weise nach: aus B folgt A
Vermutung2 basiert aber auf der Annahme: aus A folgt B - was ich nicht nachgewiesen habe
Aber mit “aus nicht-B folgt nicht-A” würde ich “aus A folgt B” nachweisen - das ist der Modus tollens, richtig?
Ich müsste also zeigen: wenn die gleichfarbigen v und w nicht Bestandteil eine bestimmten Teilgraphen sind, können sie unterschiedliche Farben annehmen, oder?

Zitat:
Nichtsdestotrotz: Herzlichen Glückwunsch zu deinem Erkenntnisgewinn! smile
…das klingt nach einem Schlusssatz - falls das so ist, nochmal vielen Dank für deine Unterstützung!
Gruß Kilian
15.11.2024, 18:20 tobit Auf diesen Beitrag antworten »

Zitat:
Ich glaub, jetzt hab ichs verstanden:
Ich weise nach: aus B folgt A
Vermutung2 basiert aber auf der Annahme: aus A folgt B - was ich nicht nachgewiesen habe

Darin sehe ich in der Tat das Kernproblem an deiner Argumentation zu Vermutung 1.

Zitat:
Aber mit “aus nicht-B folgt nicht-A” würde ich “aus A folgt B” nachweisen

Genau. Aber ich glaube nicht, dass das einfacher ist als der direkte Nachweis von "aus A folgt B".

Zitat:
das ist der Modus tollens, richtig?

Den Zusammenhang zum Modus tollens sehe ich erst einmal nicht.
Tatsächlich sind "aus A folgt B" und "aus nicht B folgt nicht A" (für beliebige Aussagen A und B) sogar äquivalent (bei der üblichen klassischen Logik), wie man z.B. durch indirekte Beweise einsehen kann.

Zitat:
Ich müsste also zeigen: wenn die gleichfarbigen v und w nicht Bestandteil eine bestimmten Teilgraphen sind, können sie unterschiedliche Farben annehmen, oder?

Das würde nicht reichen. Anscheinend hast du Teil (b) der Aussage unterschlagen:
Die Voraussetzung "nicht B" würde dir nicht liefern, dass v und w nicht Bestandteil eines bestimmten Teilgraphen sind, sondern nur, dass v und w nicht Bestandteil eines Teilgraphen sind, der gleichzeitig bestimmt und nicht mit 3 Farben färbbar ist.

(Die ganzen Verneinungen machen die Aussagen aus meiner Sicht nur komplizierter als nötig, ohne einen Erkenntnisgewinn zu liefern.)

(Ließe man die Forderung (b) in Vermutung 1 weg, wäre die entstehende Variante von Vermutung 1 leicht zu beweisen: Man betrachte einfach den (1-färbbaren) Teilgraphen V', der nur aus den Knoten v und w ohne Kanten besteht.)


Mein selbst geschriebener java-Code, mit dem ich rumexperimentiert habe, hat keine Veröffentlichungsreife... ;-)
Es ging mir nur darum, möglichst schnell einmalig die Ergebnisse zu bekommen und nicht um ein nachvollziehbares Vorgehen und einen zusammenhängenden Codestand.

Und zu den Performanceproblemen (die man vermutlich durch ein geschickteres Vorgehen als meine spontanen Schnellschüsse reduzieren kann): Beachte, dass es für 8 Knoten schon 8*(8-1)/2=28 mögliche Kanten gibt. Macht 2^28=268.435.456 (also etwa 268 Millionen) mögliche Graphen (für die z.B. für Vermutung 1 noch für jeden einzelnen Graph jeweils über alle Teilgraphen zu iterieren war). (Teilweise sind die Graphen natürlich isomorph, aber auf die Schnelle habe ich keinen Algorithmus geschrieben, der das berücksichtigt.)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » Vier-Farben-Satz Beweis