1850년경 영국 런던에 있는 대학원생이었던 구드리라는 학생은 영국의 지도에 있는 지역들을 구별하기 위한 색(colour)은 몇 가지나 될까를 생각하다가 4가지 색이면 충분할 것이라는 사실을 발견하였다. 그 후, 이 문제는 당시 복잡한 유럽지도에 국경선을 공유하는 나라들을 서로 다른 색으로 표시하는데 있어서도 4가지 색으로만 충분하다는 사실이 알려지게 되었다. 수학자들이 관심을 갖게 된 것은 ‘구면위 또는 평면위의 임의의 지도를 색칠하려면 색의 종류가 몇 가지 있어야 필요 충분할까?’ 하는 것이었고 1879년 케일리(A. Cayley)에 의하여 런던 지리학회에서 처음 공식 제기 되었다.
4색정리(四色定理) 또는 4색 문제는 평면을 유한개의 부분으로 나누어 각 부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 가지 색으로 충분하다는 정리이다. 이 문제는 지도에서 서로 맞닿은 지역에 다른 색을 칠한다는 것에서 착안해 만들어졌다. 세 가지 색으로는 평면을 칠할 수 없다는 것은 반례를 찾는 것으로 증명할 수 있다. 또한 다섯 가지 색으로 칠하는 것이 가능하다는 것도 증명되어 있다. 하지만 네 가지 색으로 가능한지에 대한 문제는 오랫동안 미해결 상태였다. 이 문제를 ‘4색 문제’(four-colour problem)라 하는데 이에 대하여 처음으로 해답을 낸 사람은 켐프라는 수학자였다. 그는 1879년부터 1880년에 걸쳐 자신의 증명을 여러 학술지에 발표하였고 일단의 논쟁은 막을 내렸다. 그로부터 11년이 지난 1899년 영국의 수학자 히우드(P.J Heawood)는 켐프의 추론과정에 결함이 있음을 발견하고, 이때부터 거의 100여 년 간에 걸쳐 이 문제는 수많은 수학자들의 관심의 대상이 되었으나 아무도 증명할 수 없었다. 그러나 이 문제에 근접하기 위한 노력은 계속되어 히우드는 다섯 가지 색으로는 어떠한 지도라도 구별 가능함을 밝혔고, 1920년경에 프랭크린(P.Franklin)은 국가수가 25개 이하인 경우에는 4색으로 구별 가능함을 증명하였다. 그 후, 1968년에는 오어와 스탬플이 40개 이하의 나라가 있으면 4색으로 구별할 수 있음을 보였지만 일반적인 해법은 발견되지 않았고, 다만 이 문제는 여러 형태의 지도와 다양한 공식들을 양산하여 점점 더 복잡한 형태로 바꾸어 졌다. 이 복잡한 여러 형태는 컴퓨터를 사용하던 수학자들에 의해 프로그램으로 저장되기 시작됐고, 마침내 이 문제는 1976년 미국의 일리노이 대학에 있는 두 수학자인 아펠과 하켄교수에 의하여 증명되었다. 그들은 고속의 컴퓨터를 이용하여 1000여 시간 이상 컴퓨터의 계산과 수 백쪽에 이르는 증명을 하였다. 그럼에도 불구하고, 수학자들은 컴퓨터를 이용한 이 증명법에 별로 흥미를 표시하지 않고 있다. 이 문제가 단순한 만큼 그 증명 또한 ‘우아하고 단순한 방법’이 존재하리라는 것이 일반적인 수학자들의 생각이다. 아펠과 하켄교수의 증명은 완벽한 것으로 검증되었지만, 그러나 증명이 지나치게 복잡하고 뿐만 아니라 증명의 대부분은 기계(컴퓨터)의 힘을 빌렸으며, 이 문제의 증명과정이 증명이외에는 쓸모가 전혀 없다는 것으로 밝혀짐으로써 누군가에 의하여 다시 증명되어야 할 문제로 남아 있다고 할 수 있다. 따라서 이 문제는 기계의 힘을 빌리지 않는 해결 방법으로는 아직까지 남아 있다고 할 수 있다.
평면을 여러 개의 부분으로 나누는 가짓수를 무한개에서 유한개로 줄인 증명이 발표된 후, 이후 이 유한개의 경우를 모두 컴퓨터 계산을 통해 검사하였다. 즉, 이 문제는 컴퓨터를 이용한 증명으로, 일부 사람들은 이러한 증명은 진정한 의미의 수학적인 증명이 아니라고 생각하고, 더욱 간단한 방법의 증명을 찾는 사람들도 있다.
아펠과 하켄은 method of discharging, rings, Kempe chains등의 복잡한 과정으로 무한히 다양한 그래프들은 유한개의 기본 그래프로 단순화시킬 수 있음을 보였고, 결국 4색 문제의 반례가 존재하지 않음을 증명할 수 있었다. 지도에서 나라가 배열되는 경우는 무한히 많지만, 결국 1936개의 단순한 형태로 줄일 수 있음을 보이고 제대로 단순화 되었는지 컴퓨터로 검사하는 방법을 썼다. 후속 연구에 따르면 633개만으로 충분하다. 무한히 많은 그래프들을 단순화시키는 과정은 두 대의 컴퓨터에서 별도로 시행하여 다시 한 번 확인하였다. 한편 기본 그래프를 네 가지 색으로 칠할 수 있음을 보이는 과정은 손으로 일일이 색을 칠하여 각각의 그래프가 4색 정리의 반례가 될 수 없음을 보이는 방법을 썼다. 이 부분만 500페이지가 넘는 분량이었으며, 많은 부분은 당시 10대 소년인 하켄의 아들 리폴드(Lippold)가 검사하였다. 컴퓨터 프로그램을 실행하는 데는 수백 시간이 걸렸다고 한다.
<이학박사, 호남수학회장, 대한수학회 부회장, 전북대학교 자연과학대학 수학과>
