Fyrfärgssatsen

Fyrfärgssatsen, eller fyrfärgsteoremet, är ett matematiskt teorem som säger att det inte behövs mer än fyra färger för att färglägga varje möjlig geografisk karta på ett sådant sätt att inga angränsande regioner har samma färg. Två regioner sägs vara angränsande om de har en gemensam gräns, inte bara en punkt.

Satsen framlades 1852 av britten Francis Guthrie. Ett kort och felaktigt bevis publicerades av Alfred Bray Kempe 1879. Felet i beviset upptäcktes 1890 av Percy John Heawood som också visade att fem färger är tillräckligt. Det är också lätt att hitta konkreta exempel där tre färger inte räcker. Att fyra färger är tillräckligt var länge en berömd obevisad hypotes och det var först 1976 som satsen slutligen bevisades av Kenneth Appel och Wolfgang Haken vid University of Illinois.^[1]

Beviset reducerade ett oändligt antal möjliga kartor till 1 936 olika situationer (senare reducerat till 1 476), varav någon måste finnas i varje tänkbar karta. Man visade sedan att om en karta innehåller någon av dessa alternativ som en del, så kan kartan förenklas, och om den förenklade kartan kan färgläggas med endast fyra färger så kan även den ursprungliga kartan det. Som hjälp att kontrollera de olika fallen användes ett datorprogram. Deras arbete dubbelkontrollerades sedan med andra program och datorer. 1996 konstruerade Neil Robertson, Daniel Sanders, Paul Seymor och Robin Thomas ett liknande bevis som krävde att 633 olika fall kontrollerades. Det nya beviset innehåller delar som kräver att en dator används och som det inte är praktiskt möjligt för en människa att själv kontrollera.

Fyrfärgssatsen var det första större teorem som bevisades med hjälp av datorer, och beviset accepterades till en början inte av alla matematiker eftersom det inte direkt enkelt kunde kontrolleras av en människa.^[1] En annan del i kritiken var avsaknaden av matematisk elegans.

• K. Appel, W. Haken, The Solution of the Four-Color-Map Problem. Scientific American 1977
• Appel, K. and Haken, W., Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989
• O'Connor and Robertson, History of the Four Color Theorem, MacTutor project, http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html
• Saaty och Kainen, The Four Color Problem: Assaults and Conquest (ISBN 0-486-65092-8)
• Robin Thomas, An Update on the Four-Color Theorem, Notices of the American Mathematical Society, Volym 45, nummer 7 (August 1998)

• Femfärgssatsen
• Rand (topologi)

• Fyrfärgssatsen på Citizendium (engelska)
• The four color problem gets a sharp new hue (engelska)