지도를 칠하는 데 네 가지 색이면 충분하다는 4색 정리

평면 위의 어떤 지도라도 경계선을 맞댄 지역끼리 서로 다른 색이 되도록 칠하려면 네 가지 색이면 충분하다. 이것이 4색 정리다. 꼭짓점 하나에서만 만나는 지역은 이웃으로 치지 않고, 한 나라가 여러 조각으로 떨어져 있지 않다는 조건이 붙는다. 질문은 단순하지만 증명은 1976년에야 나왔고, 그것도 사람이 손으로 확인할 수 없을 만큼 많은 경우를 컴퓨터가 검사한 결과였다.

한 학생의 지도에서 시작된 질문

1852년 영국의 프랜시스 거스리는 영국 지도의 주들을 칠하다가 네 가지 색으로 늘 충분해 보인다는 점을 알아챘다. 이 질문은 그의 동생을 거쳐 수학자 오거스터스 드모르간에게 전해졌고, 곧 수학자들 사이에 퍼졌다.

세 가지 색으로는 부족한 지도가 있다는 것은 쉽게 보일 수 있다. 가운데 한 나라를 세 나라가 둘러싸고, 그 세 나라가 서로 모두 맞닿아 있으면 네 나라가 서로 이웃이 된다. 이때는 네 가지 색이 반드시 필요하다. 어려운 것은 반대 방향, 곧 다섯 번째 색이 필요한 지도가 절대 없다는 것을 보이는 일이었다.

지도를 점과 선으로 바꾸기

수학자들은 지도를 그래프로 바꾸어 생각한다. 나라마다 점을 하나 찍고, 국경을 맞댄 두 나라의 점을 선으로 잇는다. 그러면 지도 칠하기는 선으로 이어진 두 점이 같은 색이 되지 않도록 점에 색을 칠하는 문제가 된다. 평면 지도에서 나온 그래프는 선이 서로 엇갈리지 않게 그릴 수 있는데, 이런 그래프를 평면 그래프라고 한다.

평면 그래프에는 중요한 성질이 하나 있다. 이웃이 다섯 개 이하인 점이 반드시 하나는 있다는 것이다. 이 사실은 오일러가 밝힌 점, 선, 면의 개수 사이의 관계에서 나온다. 이 성질 덕분에 다섯 가지 색이면 충분하다는 5색 정리는 비교적 짧게 증명된다. 이웃이 적은 점을 하나 빼고 나머지를 칠한 뒤, 그 점을 되돌려 놓으며 남는 색을 찾는 방식이다.

틀린 증명이 남긴 도구

1879년 영국의 앨프리드 켐프가 4색 정리의 증명을 발표했고, 이 증명은 11년 동안 맞는 것으로 받아들여졌다. 1890년 퍼시 히우드가 그 안의 빈틈을 찾아냈다. 히우드는 켐프의 방법을 고쳐 5색 정리를 증명하는 데 성공했지만, 네 가지 색의 문제는 다시 미해결로 돌아갔다.

켐프의 증명은 틀렸지만 그가 쓴 방법은 살아남았다. 두 가지 색만 번갈아 칠해진 사슬을 찾아 두 색을 맞바꾸는 기법으로, 오늘날 켐프 사슬이라고 부른다. 뒤의 증명들은 모두 이 생각을 바탕으로 했다.

컴퓨터가 확인한 증명

1976년 미국 일리노이 대학의 케네스 아펠과 볼프강 하켄은 다른 길을 택했다. 만약 다섯 가지 색이 필요한 지도가 있다면, 그중 나라 수가 가장 적은 지도가 있을 것이다. 두 사람은 그런 지도라면 반드시 품고 있어야 하는 작은 모양들의 목록을 만들고, 그 모양들이 하나하나 가장 작은 반례가 될 수 없음을 보였다. 목록에 오른 모양은 거의 2천 개에 이르렀고, 각 모양을 검사하는 일은 컴퓨터가 1천 시간 넘게 계산해서 끝냈다.

이 증명은 큰 논쟁을 불렀다. 사람이 처음부터 끝까지 따라 읽을 수 없는 증명을 증명이라고 부를 수 있느냐는 물음이었다. 1996년 다른 연구진이 검사할 모양을 600여 개로 줄인 더 깔끔한 증명을 내놓았고, 2005년에는 증명의 모든 단계를 컴퓨터 증명 검사 프로그램으로 다시 확인하는 작업이 이루어졌다. 지금 4색 정리를 의심하는 수학자는 거의 없다.

4색 정리는 평면과 공 표면 위의 지도에만 해당한다. 도넛 모양의 표면 위에 그린 지도에서는 서로 모두 이웃한 지역을 일곱 개까지 만들 수 있어서, 일곱 가지 색이 필요하다. 히우드는 표면에 뚫린 구멍의 수에 따라 필요한 색의 수를 계산하는 식을 내놓았고, 이 식은 평면을 뺀 거의 모든 경우에 대해 먼저 증명되었다. 가장 단순해 보이는 평면이 오히려 가장 늦게 풀린 셈이다.

아직 남은 질문

4색 정리는 참으로 받아들여지지만, 사람이 읽고 이해할 수 있는 짧은 증명은 아직 없다. 많은 수학자가 이 정리가 왜 참인지를 한눈에 보여 주는 설명이 어딘가에 있으리라 기대한다. 또 실제 지도에서 네 가지 색으로 칠하는 방법을 찾는 일은 쉽지만, 주어진 그래프를 세 가지 색으로 칠할 수 있는지 판정하는 일은 매우 어려운 문제로 알려져 있다. 같은 칠하기 문제라도 색 하나 차이로 난이도가 크게 달라지는 이유는 계산 이론의 깊은 질문과 이어져 있다.