4색 정리(四色定理) 또는 4색 문제는 평면을 유한개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리이다. 이 문제는 지도에서 서로 맞닿은 지역에 다른 색을 칠한다는 것에서 착안해 만들어졌다. 세 가지 색으로는 평면을 칠할 수 없다는 것은 반례를 찾는 것으로 증명할 수 있다. 또한 다섯 가지 색으로 칠하는 것이 가능하다는 것도 증명되어 있다. 하지만 네 가지 색으로 가능한지에 대한 문제는 오랫동안 미해결 상태였다. 평면을 여러 개의 부분으로 나누는 가짓수를 무한개에서 유한개로 줄인 증명이 발표된 후, 이후 유한개의 경우를 모두 컴퓨터 계산을 통해 검사하였다. 즉, 이 문제는 컴퓨터를 이용한 증명으로, 일부 사람들은 이러한 증명은 진정한 의미의 수학적인 증명이 아니라고 생각하고, 더욱 간단한 방법의 증명을 찾는 사람들도 있다.
4색 문제를 처음으로 연구한 사람은 프랜시스 구드리(Francis Guthrie)이다. 1852년에 영국의 지도를 색으로 칠해 구분하다가, 네 가지 색만 사용하면 각 주(州)를 구분할 수 있다는 것을 발견하였다. 구드리는 자신의 스승인 드모르간에게 이것을 수학적으로 증명할 수 있는지 문의하였다. 구드리는 유니버시티 대학에서 드모르간의 학생이었으며 1850년에 졸업하였다. 4색정리가 처음으로 학문적으로 논의된 것은 1879년 아서 케일리의 논문이었다. 4색정리를 증명하기 위한 시도는 여러번 있었다. 1879년에 알프레드 켐프가 4색 정리 증명을 발표하였고, 많은 사람이 증명 과정이 옳다고 생각하였다. 이듬해에는 피터 테이트(가 다른 방법으로 4색 정리를 증명하였다. 1890년이 되어서야 퍼시 히우드에 의해서 켐프의 증명에서 오류가 있다는 것이 밝혀졌고, 1891년에는 율리우스 페터센에 의해서 테이트의 증명도 잘못되었다는 것이 밝혀졌다. 증명이 잘못되었다는 것이 모두 11년이 지나서야 밝혀진 것이다. 히우드는 켐페의 증명이 잘못되었다는 것뿐 아니라, 모든 평면 그래프는 다섯 가지 색을 사용하면 구분 가능하다는 것을 증명하였다. 이것을 4색정리와 구분하여 5색정리라고 한다.
독일의 수학자 하인리히 헤쉬는 컴퓨터로 수학적 증명을 해결하는 방법을 제안하였다. 드디어 1976년에 일리노이 대학교 어바나-샴페인의 케네스 아펠과 볼프강 하켄이 히쉬의 기본 아이디어에 코흐 의 알고리즘을 더하여 4색 정리를 증명하는 데에 성공하였다. 만약 4색정리가 거짓이면, 다섯 가지 색이 필요한 구획들로 구성된 지도가 적어도 하나 존재할 것이다. 아펠과 하켄은 그런 반례가 존재하지 않는다는 것을 다음과 같은 두 가지 개념을 이용하여 보였다.
지도에서 나라들이 배열되는 경우의 수는 무한히 많지만, 그 형태를 단순화시키면 유한개의 기본 그래프가 조합된 형태가 된다. 기본 그래프가 4색 문제의 반례가 되지 않고, 나머지 부분을 네 가지 색으로 칠할 수 있으면 전체 그래프는 네 가지 색으로 칠할 수 있다. 아펠과 하켄은 method of discharging, rings, Kempe chains등의 복잡한 과정으로 무한히 다양한 그래프들은 유한개의 기본 그래프로 단순화시킬 수 있음을 보였고, 결국 4색 문제의 반례가 존재하지 않음을 증명할 수 있었다. 지도에서 나라가 배열되는 경우는 무한히 많지만, 결국 1936개의 단순한 형태로 줄일 수 있음을 보이고 제대로 단순화 되었는지 컴퓨터로 검사하는 방법을 썼다. 후속 연구에 따르면 633개만으로 충분하다. 무한히 많은 그래프들을 단순화시키는 과정은 두 대의 컴퓨터에서 별도로 시행하여 다시 한 번 확인하였다. 한편 기본 그래프를 네 가지 색으로 칠할 수 있음을 보이는 과정은 손으로 일일이 색을 칠하여 각각의 그래프가 4색 정리의 반례가 될 수 없음을 보이는 방법을 썼다. 이 부분만 500페이지가 넘는 분량이었으며, 많은 부분은 당시 10대 소년인 하켄의 아들 리폴드가 검사하였다. 컴퓨터 프로그램을 실행하는 데는 수백 시간이 걸렸다.
어떤 지도를 한 가지 혹은 두 가지 색으로 칠할 수 있는지 여부를 판별하는 효율적인 알고리즘은 존재하지만, 세 가지 색으로 칠할 수 있는지 여부는 NP-완전 문제이기 때문에 빠른 해결방법이 없을 것으로 추측된다. 어떤 그래프가 평면 그래프이든 아니든 네 가지 색으로 칠할 수 있는지 여부를 판별하는 문제도 마찬가지로 NP-완전이다. 한편으로는 지도를 실제로 네 가지 색으로 칠하는 알고리즘은 시간 복잡도로 가능함이 알려져 있다.
