El teorema dels cinc colors és un resultat de la teoria de grafs que estableix que en un pla separat en regions, com ara un mapa polític de les províncies d'un estat, les regions es poden acolorir utilitzant no més de cinc colors de manera que no hi hagi dues regions adjacents que rebin el mateix color.
El teorema de cinc colors és conseqüència directa del més fort teorema dels quatre colors, però és considerablement més fàcil de demostrar. Es basa en un intent fallit de demostrar el teorema dels quatre colors per part d'Alfred Kempe el 1879. Percy John Heawood hi va trobar un error 11 anys després, i va demostrar el teorema dels cinc colors basant-se en el treball de Kempe. El teorema dels quatre colors va ser finalment demostrat per Kenneth Appel i Wolfgang Haken de la Universitat d'Illinois amb l'ajuda d'un ordinador. Van rebre l'assistència de John A. Koch en algunes parts del disseny algorítmic.
Bibliografia
- Heawood, P. J. «Map-Colour Theorems». Quarterly Journal of Mathematics, Oxford, 24, 1890, p. 332–338.
Vegeu també
