4색정리

1 개요

Four color theorem

인접한 나라끼리 겹치지 않게끔 지도 위의 모든 나라를 색칠하는데, 4가지 색만으로도 충분한지에 대한 문제. 4색 지도, 4색 문제, 4색 정리, 4색 증명 등 여러 이름으로 불린다.

2 발단

앞선 시기에 독일의 수학자 뫼비우스가 4색 문제를 먼저 거론했다는 기록이 있긴 하지만, 이 문제가 본격적으로 알려진 것은, 집합과 관련된 법칙으로 더 친숙한 영국의 수학자 드모르간 때문으로 알려져 있다.

1852년 영국의 식물학자 프란시스 구스리(Fransis Guthrie)가 영국 지도를 구획 별로 색칠하던 중, 4가지색만 있으면 인접한 지역끼리 서로 겹치지 않게 칠할 수 있다는 것을 알게 되었다. 동생 프레드릭은 형에게 들은 지도와 4가지색에 대한 이야기를 저명한 수학자 드모르간에게 묻게 되고, 이후 드모르간 본인을 포함하여 수많은 수학자들이 4색 문제에 뛰어들게 된다.

3 증명 과정

전문 용어가 난무하는 다른 난제들과 달리, 어린아이도 이해할 수 있는 간단한 문제라서 일반인들도 많이 도전하였으며, 어린아이 수준이라고 얕보고 자신만만하게 증명을 시도했다가 낭패를 본 수학자도 여럿 있었다.

4색 문제를 자신이 해결했다는 사람은 많았으나, 대부분은 엉터리였고, 수학자들조차도 부분적, 간접적 증명에서 더 이상 발을 떼지 못하고 있는 상황에서 1879년 알프레드 켐프(Alfred Kempe)가 증명을 내놓으면서 4색 문제에 종지부를 찍는 것으로 보였으나, 11년 뒤에 증명 과정의 오류가 밝혀지며 문제는 다시 원점으로 돌아온다. 오류를 밝힌 퍼시 히우드(Percy Heawood)는 켐프의 정리를 손질하여 5색으로는 가능하다는 5색 정리를 증명하는데 성공한다.

1960년대 독일의 헤쉬는 컴퓨터한테 증명을 시키면 어떨까?하는 당시로서 획기적인 생각을 한 뒤, 증명에 필요한 컴퓨터를 구하기 위해 독일과 미국을 동분서주하며, 기초 이론을 세웠지만, 패전한 서독의 경제사정 탓이었는지 연구 자금 중지 크리를 맞고, 증명에 실패한다.

그 후 1976년 미국의 볼프강 하켄, 케네스 아펠이 헤쉬의 아이디어를 가지고서 컴퓨터 두 대를 50여일 가량 돌린 끝에 증명에 성공한다.

4 컴퓨터를 통한 최초의 증명

이들의 기본적인 생각은, 공식이나 법칙을 모르면 시험지에 일일이 노가다로 그려서 문제를 풀 듯, 컴퓨터를 이용해서 가능한 모든 경우의 지도 모델을 뽑고, 거기에 4색 정리가 적용되는지 안 되는지를 가려보자는 것이다. 모든 계산이 끝난 뒤에 하나의 반례도 없으면, 4색 정리는 끝나는 것이고, 반례가 나오더라도, 그 자체로 4색 정리는 거짓이라고 밝혀지며 4색 문제가 해결되는 매우 간단한 방법이었다. 그 과정이 쌩노가다이긴 하지만

앞서 헤쉬가 기초 이론을 세우던 과정에서 검토해야할 지도의 모델 개수는 만개 정도 였다고 하지만, 하켄과 아펠은 모델을 더욱 단순화 시키는 방법으로 1936개까지 줄이는데 성공하였다. 하켄과 아펠은 여기에 487가지 판별 필터를 걸고 두 대의 컴퓨터를 따로 돌려서 같은 결과가 나오는 것을 확인 하고 해당 결과물을 일일이 손으로 색칠하는 방법으로 모든 모델의 지도를 인접 구획끼리 겹치지 않게 4색 이하로 색칠하고, 하켄의 아들이 다시 재확인 하는 방법으로 증명에 성공하였다.

그러하다보니 증명 결과만 몇 박스에 달했고, 여러 수학자들 앞에서 멋지게 수식을 휘날리며, 결론을 도출한 뒤 과정에 오류가 없음을 확인받는 기존의 증명과 달리, 컴퓨터로 계산해서 빼먹은 것 없는지 확인 다 했고, 그 결과물이 이거다라며 종이 몇 박스를 들이미는 식이라 여러 수학자들에게 아름답지 못한 증명이라며 까이게 된다. 가능한 모든 사례를 검토해 본 결과 반례가 없으므로 증명 완료라는 주먹 구구식 방법을 내놓기도 했지만, 최초로 컴퓨터를 사용한 증명이라는 점 역시, 인간이 검증 할 수 없는 증명이라는 이유로 기존 수학자들의 반감을 사게 되었다. 실제로 당시의 기록들을 살펴보면, 검토 결과 그들의 증명 과정에서 오류를 찾을 수는 없었고, 그들이 컴퓨터를 통해 4색 문제를 증명해낸 것은 반박할 수 없는 사실이지만, 그래도 컴퓨터를 가지고 이런 무식한 방법으로 증명한 점에서 그들은 까여야함.이라는 수많은 수학자들의 비판을 찾아 볼 수 있다. 팩트폭력당한 수학자들

오늘날에야 누구나 다 컴퓨터를 가지고 있고, 이 정도 계산은 몇 초도 지나지 않아 끝나므로 그까짓거 컴퓨터에 명령어만 몇 개 입력하고 시행 버튼만 누르면 끝이니 저능아도 하겠네라고 생각할 수 있겠지만 하켄과 아펠은 수 년에 걸쳐 그들의 이론과 판별식을 가다듬고, 계산을 수행할 컴퓨터와 연구에 필요한 자금을 얻기 위해 노력했다. 2천여 시간 동안 하드를 불태우며 작업을 수행한 것은 컴퓨터이지만, 컴퓨터는 어디까지나 계산 도구였을 뿐 컴퓨터에 돌릴 수 있도록 케이스를 줄이고 모든 준비와 검토, 발표를 담당한 하켄과 아펠의 공로를 무시해서는 안 된다.

5 4색 문제 증명 이후

수많은 수학 난제들이 그러하듯, 증명 자체에는 별 도움이 되지 않았을지 몰라도, 그 과정에서 나온 수많은 중간 결과물들이 다른 난제를 푸는데 도움이 되거나, 새로운 난제를 낳게 되었다. 4색 문제를 통해 위상수학과 그래프 이론이 한층 더 발전할 수 있었고, 복잡한 계산이나 모델화, 검증과 같은 증명 과정에 컴퓨터를 사용하는 것이 일반화 되면서, 이제 컴퓨터는 수학과 뗄 수 없는 도구가 되었다.

지금은 그래프 색칠 관련 문제로 여겨지지만, 4색 문제의 출발점은 지도색칠 문제였다. 4가지 색만 가지고도 지도를 색칠하는게 가능하다는 것이 증명되기는 하였지만, 지도 색칠은 색을 적게 쓰는 것보다는 알아보기 편하도록 적재적소에 알맞은 색을 쓰는 것이 중요하므로 지도 작업 도중 A:너 그거 알아? 지금 우리가 만드는 지도 4가지 색만 가지고도 칠하는 게 가능하대. B:아! 4색 문제 말이지. 나 그거 들어 봤어.라는 이야깃거리가 생긴 것 이상의 성과는 없었다.

실제로도 지도를 그릴 때 4가지 색만 가지고 칠하는 게 불가능한 경우들이 있는데, 연못이나 호수를 바다와 같이 푸른색으로 통일하면 4가지 색으로는 불가능할 경우가 발생한다. 그래도 이는 바다나 연못 등에 쓰이는 색을 별색처리하고 나머지 4색으로 하면 가능은 하다. 같은 맥락으로 월경지가 있어서 월경지와 본토를 같은 색으로 칠해야 해서 4가지 색만으로 불가능해지는 경우가 생기기도 한다.