Lexikon der Mathematik: Vier-Farben-Satz
sagt aus, daß jede Landkarte eines planaren Graphen eine Färbung mit vier Farben besitzt.
Eine mit vier Farben gefärbte Landkarte.
Der Vier-Farben-Satz ist einer der berühmtesten und tiefsten Sätze der Graphentheorie, und die vielfältigen und oft vergeblichen Versuche, ihn zu beweisen, haben etliche Zweige der Graphentheorie erst entstehen lassen.
Seine Aussage geht auf eine Beobachtung von F. Guthrie, einem Londoner Studenten, aus dem Jahr 1852 zurück, und fand über A. deMorgan und A. Cayley als offenes Problem Eingang in die Mathematik. Der erste, 1879 von A.B. Kempe veröffentlichte, fehlerhafte Beweis enthält mit den sogenannten Kempe-Ketten bereits ein wesentliches Element vieler späterer Beweisversuche. Der Fehler in diesem Beweis wurde erst 1890 von P.J. Hea-wood entdeckt.
Fast ein ganzes Jahrhundert lang blieb der Satz als Vier-Farben-Problem eine offene Vermutung. Der erste weitgehend akzeptierte, aber sehr komplizierte Beweis geht auf das Jahr 1976 zurück und stammt von K. Appel und W. Haken. Einige der von ihnen benutzten zentralen Ideen gehen bereits auf Arbeiten von H. Heesch aus dem Jahr 1969 zurück. Da weite Teile des Beweises von Appel und Haken nur mittels eines Computers überprüfbar sind, blieb er umstritten. Ihre Beweismethode besteht darin, eine unvermeidbare Menge von reduzierbaren Konfigurationen in einem minimalen Gegenbeispiel anzugeben. Dabei bedeutet „unvermeidbar”, daß jedes minimale Gegenbeispiel mindestens eine dieser Konfigurationen enhalten muß, und „reduzierbar”, daß sich mit Hilfe jeder dieser Konfigurationen ein kleineres Gegenbeispiel konstruieren ließe, was im Widerspruch zur Wahl des Gegenbeispiels steht und daher die Aussage beweist.
1997 fanden N. Robertson, D.P. Sanders, P. Seymour und R. Thomas unter Benutzung derselben Methode einen wesentlich kürzeren Beweis des Vier-Farben-Satzes, der allerdings immer noch Teile enthält, die mit einem Computer verifiziert werden müssen.
[1] Aigner, M.: Graphentheorie, Eine Entwicklung aus dem Vier-Farben-Problem. Teubner-Verlag Stuttgart, 1984.
[2] Fritsch, R.: Der Vierfarbensatz. Geschichte, topologische Grundlagen und Beweisidee. B.I.-Wissenschaftsverlag Mannheim, 1994.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.