4색 정리(Four color theorem)

1852년 런던에서 수학을 공부한 젊은 영국인 프랜시스 거스리(뒤에 남아프리카에서 수학 교수가 되었습니다)는 잉글랜드의 주(州)들을 지도에 칠하다가 네 가지 색이면 늘 충분해 보인다는 것을 알아챘습니다. 규칙은 하나입니다. 경계선을 한 토막 이상 나누는 이웃 나라는 다른 색이어야 합니다(한 점에서만 만나는 나라는 이웃으로 치지 않습니다). 그리고 나라마다 땅이 한 덩어리여야 합니다. 떨어진 영토를 같은 색으로 칠해야 한다면 다섯 색 이상이 필요한 지도를 만들 수 있습니다. 나라를 꼭짓점⁠(vertex)⁠으로, 이웃 관계를 변으로 바꾸면 지도는 변이 서로 엇갈리지 않게 평면에 그릴 수 있는 그래프가 되고, 문제는 이웃한 꼭짓점이 다른 색이 되게 칠하는 것이 됩니다.

나라를 눌러 색을 바꿔 보세요. 누를 때마다 다음 색으로, 네 번째 색 다음에는 빈칸으로 돌아갑니다. 같은 색 이웃 사이의 경계는 빨갛게 표시됩니다.

순서대로 칠하기 되추적으로 칠하기() 지우기 새 지도 ·

세 가지 색으로는 부족한 지도가 있습니다. 벨기에, 프랑스, 독일, 룩셈부르크처럼 서로 모두 맞닿은 네 나라가 있으면 네 색이 모두 필요합니다. 반대로 다섯 나라가 서로 모두 맞닿는 지도는 평면에 그릴 수 없습니다. 그런 지도가 있다면 네 색으로 칠할 때 비둘기집 원리⁠(pigeonhole principle)⁠에 따라 두 나라가 같은 색이 될 테니까요. (이 사실 자체는 4색 정리 없이, 아래에 나오는 오일러의 다면체 공식⁠(polyhedron formula)⁠으로 쉽게 증명됩니다.) 흔히 '서로 모두 맞닿은 다섯 나라가 없으니 네 색이면 된다'고 생각하지만, 이것만으로는 4색 정리가 나오지 않습니다. 한 나라를 다섯 나라가 고리처럼 둘러싼 지도를 보면, 서로 모두 맞닿은 나라는 셋뿐인데도 네 색이 필요합니다(고리의 다섯 나라에 이미 세 색이 들고, 가운데 나라에 넷째 색이 듭니다). 서로 모두 맞닿은 무리의 크기만으로는 필요한 색의 수를 알 수 없습니다.

'순서대로 칠하기'는 나라를 번호 순으로 보며, 이웃이 아직 쓰지 않은 가장 앞 색을 고르는 욕심쟁이 방법⁠(greedy algorithm)⁠입니다. 빠르지만 앞의 선택을 되돌리지 않아서 다섯째 색(보라)이나 그 이상이 필요해질 때가 있습니다. 이 지도에서는 . '되추적⁠(backtracking)⁠'은 막히면 바로 앞 나라로 돌아가 다른 색을 시도합니다. 나라가 n개일 때 규칙을 따지지 않고 네 가지 색을 나눠 주는 방법은 모두 $4^n$가지, 곧 n자리 4진수의 개수이지만, 되추적은 막힌 가지를 일찍 잘라 냅니다. 이 지도에서 다 칠하고 나면 같은 색 나라들의 모임이 나라 전체를 서로 겹치지 않는 묶음으로 나눕니다(동치류⁠(equivalence class)⁠로 나눈 분할).

1879년 영국의 변호사이자 수학자 앨프리드 켐프가 4색 정리의 증명을 발표했지만, 1890년 영국의 수학자 퍼시 히우드가 그 안의 틀린 곳을 찾아냈습니다. 히우드는 같은 논문에서 켐프의 생각을 살려 다섯 색이면 충분하다는 것을 짧게 증명했습니다. 출발점은 오일러의 다면체 공식 $V - E + F = 2$입니다. 변이 엇갈리지 않게 평면에 그린 한 덩어리 그래프에서 V는 꼭짓점 수, E는 변 수, F는 변들이 평면을 나눈 면의 수(바깥의 넓은 영역도 하나로 셉니다)이고, 이 셋이 늘 이 관계를 만족합니다. 같은 두 점을 잇는 변이 여럿이 아니면, 면마다 변이 적어도 셋 둘러싸고 변 하나는 면 두 개에 닿으므로 $2E \ge 3F$입니다. 이것을 공식에 넣으면 $E \le 3V - 6$이 나옵니다(꼭짓점이 셋 이상일 때). 차수의 합은 2E이니 차수의 평균⁠(mean)⁠은 $2E/V \le 6 - 12/V$, 곧 6보다 작고, 따라서 이웃이 다섯 이하인 나라가 반드시 있습니다. 그 나라를 떼어 낸 작은 지도를 먼저 칠하고 되돌려 놓는 수학적 귀납법⁠(mathematical induction)⁠이 증명의 뼈대입니다. 이웃이 넷 이하이면 남는 색이 있습니다. 이웃이 다섯이고 다섯 색을 모두 쓰고 있으면, 켐프가 고안한 방법으로 두 색이 번갈아 이어진 사슬의 색을 서로 바꾸어 색 하나를 비워 줍니다. 이 공식의 주인 오일러는 오일러 경로⁠(Euler path)⁠로 그래프 이론⁠(graph theory)⁠을 처음 연 바로 그 사람입니다.

네 색은 훨씬 어려웠습니다. 1976년 미국 일리노이 대학교의 케네스 아펠과 볼프강 하켄은 먼저 어떤 지도에든 적어도 하나는 반드시 들어 있는 작은 모양(배치) 천수백 개의 목록을 만들었습니다. 그리고 그 하나하나가 '줄일 수 있다'는 것, 곧 그 모양을 품은 지도가 네 색으로 칠할 수 없는 가장 작은 지도일 수는 없다는 것을 컴퓨터로 확인했습니다. 가장 작은 반례에도 목록의 모양 하나가 들어 있어야 하는데 그럴 수 없으니, 반례는 없습니다. 사람이 손으로 다 검토할 수 없는 증명이라 논란이 되었습니다. 1996년 로버트슨, 샌더스, 시모어, 토머스가 배치를 633개로 줄인 더 간결한 증명(역시 컴퓨터가 필요)을 내놓았고, 2005년에는 조르주 공티에가 증명 보조기⁠(proof assistant)⁠ Coq(증명의 모든 단계를 논리 규칙에 맞는지 기계적으로 확인하는 프로그램)로 증명 전체를 형식 검증⁠(formal verification)⁠했습니다.

k가지 색으로 이웃끼리 다르게 칠하는 방법의 수를 $P(k)$라 하면, 이것은 k에 대한 다항식⁠(polynomial)⁠이 되어 채색 다항식⁠(chromatic polynomial)⁠이라 부릅니다. 예를 들어 서로 모두 이어진 세 점(삼각형)은 첫 점에 k가지, 둘째 점에 k − 1가지, 셋째 점에 k − 2가지 색을 줄 수 있어 $P(k) = k(k-1)(k-2)$입니다. 일반적인 그래프에서는 '이 변의 양 끝이 같은 색'이라는 나쁜 조건들을 모아 포함배제 원리⁠(inclusion–exclusion principle)⁠로 셉니다. 나쁜 조건을 고른 변들의 모임마다 더하거나 빼므로, 변 집합⁠(set)⁠의 모든 부분집합⁠(subset)⁠, 곧 멱집합⁠(power set)⁠에 대한 합이 됩니다.

이어지는 곳. 구면 위의 지도도 네 색이면 됩니다. 구면에서 한 점을 빼면 평면으로 펼칠 수 있기 때문입니다. 반면 도넛 모양의 원환면⁠(torus)⁠ 위에서는 일곱 색이 꼭 필요한 지도가 있습니다(그리고 일곱 색이면 늘 충분합니다). 색칠은 '부딪치는 것끼리 다른 칸에' 넣는 문제의 모형입니다. 시험 시간표라면 과목이 점, 같은 학생이 듣는 두 과목 사이가 변, 시간대가 색입니다. 방송국의 주파수 배정, 그리고 프로그램에서 동시에 쓰이는 변수들을 컴퓨터 안의 서로 다른 저장 칸(레지스터)에 넣는 일도 같은 모양입니다.

네 가지 색이면 충분하다는 것은 증명되었지만, 주어진 지도를 세 가지 색으로 칠할 수 있는지 가리는 일은 NP-완전⁠(NP-complete)⁠ 문제입니다. 칠한 결과를 보여 주면 맞는지 확인하기는 쉽지만, 빠르게 칠하는 방법은 알려져 있지 않고, 이런 부류에서 가장 어려운 문제라는 뜻입니다(P 대 NP 문제⁠(P versus NP problem)⁠). 컴퓨터가 증명을 도왔다는 사실은 '사람이 끝까지 읽을 수 없는 증명도 증명인가'라는 물음을 불러냈습니다. 증명을 기계가 규칙대로 확인할 수 있는 기호의 나열로 보는 관점, 그리고 그렇게 본 증명이 할 수 없는 일은 괴델의 불완전성 정리⁠(incompleteness theorem)⁠가 다룹니다.