📂그래프이론

4색 지도 문제

빌드업

4색 지도 문제란 어떤 지도든 이웃된 구역이 서로 구별되도록 채색하는데 4가지 색이면 충분한지 묻는 문제다. 지도가 복잡할수록 색은 많아져야할 것 같지만, 바로 옆이랑만 다르면 되기 때문에 생각보다 많은 색이 필요하지는 않다. 예를 들어 다음은 세계지도를 단 $4$가지 색으로 칠한 것이다.

역사적으로 4색 지도 문제는 1852년 영국의 식물학자 프랜시스 구드리^{francis Guthrie}가 영국의 지도를 색으로 칠해 구분하다가 단 4가지 색만 사용해서 각 주를 구분할 수 있다는 것을 발견하고, 드 모르간의 정리로도 유명한 스승 드 모르간 에게 수학적으로 증명할 수 있는지 물었다. 4색 문제가 학구적으로 진지하게 언급된 것은 1879년 아서 케일리의 논문이 최초였다고 한다. 4색 문제는 수학적으로 다음과 같이 진술된다.

임의의 지도는 $4$-채색가능한가?

수학, 특히 그래프 이론에서 지도란 $3$-연결 평면 그래프로 정의된다.

이후 1879년 알프레드 켐프^{alfred kempe} 와 1880년 피터 테이트^{peter Tait}가 4색 정리를 증명했지만, 각각 11년 뒤 퍼시 히우드^{percy Heawood} 와 줄리우스 피터슨^{julius Petersen}에 의해 증명의 오류가 발견되었다. 히우드는 대신 $5$가지 색으로는 지도를 채색할 수 있다는 5색 정리를 증명했다.

4색 문제는 언뜻 간단해보이지만 이 ‘임의의 지도’라는 게 생각보다 만만한 조건이 아니었다. 5색 정리에서 단 한가지 색을 줄일 뿐인데 무수히 많은 경우의 수라는 허들이 증명의 발목 잡았다. 이에 1976년, 아펠^appel 과 하켄^haken은 지도의 형태를 단순화해서 유한한 경우의 수로 줄이고, 그 모든 경우를 컴퓨터로 검토하는 방식으로 4색 문제를 풀어버린다.

아펠-하켄 4색 정리 ¹

임의의 지도는 $4$-채색가능하다.

의의

컴퓨터를 이용한 증명은 당대에 큰 논란이 되었으며, 이후에도 많은 공격을 받았다. 순수 수학의 아름다움에 매료된 이들에게 있어서 1936개의 케이스를 일일이 확인하는 것은 별로 수학답지 않다고 보였을지도 모르고, 그것이 진정 증명이라 부를 수 있는 것인지 의문을 제기하는 사람도 있었다. 그러나 어찌됐든 아펠과 하켄의 증명은 논의된지 딱 100년 된 난제를 풀어낸 최초의 해답으로 인정받고 있다.