Überlegungen zum Vier-Farben-Satz
Auch wenn ich der Ausbildung nach nicht Mathematiker bin, habe ich mir zum Vier-Farben-Satz (siehe Wikipedia) mehrmals Gedanken gemacht. Da ich in meiner Diplomarbeit in Informatik auch ein graphentheoretisches Thema behandelt habe, bin ich in gewissem Sinne sogar dafür qualifiziert, mir zu diesem Problem Gedanken zu machen. Grundsätzlich ist das Vier-Farben-Problem natürlich schon gelöst, deswegen spricht man ja auch vom Vier-Farben-Satz. Aber der Beweis ist eben nicht gerade elegant. Im Originalbeweis werden über 1400 Fälle unterschieden. Erst vor weniger als 20 Jahren gelang es, die Fallunterscheidungen auf weniger als die Hälfte zu reduzieren. Wer weiß, vielleicht ist selbst das noch redundant. Ich hatte jedenfalls heute im Schlaf folgenden Einfall: Gegeben ist ein einfacher, ungerichteter Graph G. Wenn zwei Knoten durch eine Kante verbunden sind, bedeutet das, dass sie im reduzierten Graphen G' voneinander verschieden sein müssen. Der reduzierte Graph G' sei der minima