사색정리
네 가지 색이면 충분합니다
종이에 나라들이 국경을 맞대고 있는 복잡한 가상 지도를 마음대로 그려 보세요. 이웃한 나라끼리 다른 색이 되도록 색칠을 시작합니다.
세 가지 색으로는 금방 막히지만, 네 가지 색만 있으면 아무리 복잡한 지도도 다 칠할 수 있습니다. 정말 다섯 번째 색이 필요한 지도는 없을까요?
이야기
ActiviaYogurt
CC0 · 위키미디어 공용
세계 지도를 색칠하는데, 이웃한 나라는 다른 색이어야 합니다. 색이 몇 가지나 있어야 할까요?
직접 해 보세요. 아무리 복잡하게 그려도 네 가지면 충분합니다. 세 가지로는 안 되는 지도를 금방 만들 수 있지만, 다섯 가지가 필요한 지도는 아무도 만들지 못했습니다.
이 물음이 나온 것은 1852년입니다. 그런데 증명되기까지 124년이 걸렸습니다. 1976년, 케네스 아펠과 볼프강 하켄이 해냈습니다.
그런데 그 증명이 논쟁을 일으켰습니다. 경우를 1936가지로 줄인 다음, 컴퓨터로 하나씩 확인했기 때문입니다. 사람이 손으로 다 읽을 수 없는 증명이었습니다.
“사람이 확인할 수 없는 것도 증명인가?” 이 물음은 지금도 살아 있습니다. 다만 그 뒤로 컴퓨터의 도움을 받은 증명은 점점 늘고 있습니다.
서로 부딪히면 안 되는 것을 나누는 문제입니다. 지도 색칠은 그 가장 쉬운 얼굴일 뿐입니다.
휴대전화 기지국의 주파수 배정, 시험 시간표 짜기, 컴파일러가 변수를 레지스터에 넣는 일이 모두 같은 문제입니다.
계단 넷 — 같은 사실을 네 깊이로
지도를 직접 칠해 본다
종이에 원을 그리고 피자 조각처럼 셋으로 나눈 뒤 가운데에 작은 원을 하나 그려 보세요. 가운데 나라와 둘레의 나라 셋이 서로 모두 닿아 있습니다.
색연필을 들고 칠해 봅니다. 세 색으로는 이웃한 나라가 같은 색이 되어 버리지만, 네 번째 색을 쓰면 완벽하게 칠해집니다. 직접 지도를 그리며 색을 채워 보세요.
지도를 색칠해 보세요
세상에 나라가 수백 개 있어도 색연필은 딱 4자루만 있으면 색칠 공부를 끝낼 수 있다
왜 세 색으로는 안 되나
한 점을 둘러싸고 홀수 개의 영역(예: 3개 또는 5개)이 바퀴살처럼 둘러싸고 있으면, 둘레를 번갈아 칠하는 데 이미 3가지 색이 필요합니다.
여기에 가운데 영역이 둘레의 모든 영역과 국경을 맞대고 있으므로, 가운데 영역에는 반드시 네 번째 새로운 색이 쓰여야 합니다. 이 단순한 구조만으로도 3가지 색으로는 불가능함을 쉽게 알 수 있습니다.
색이 몇 가지 필요한가
다섯 나라가 둥글게 둘러싸고 가운데 대장 나라가 있으면 색연필 3자루로는 무조건 부딪힌다
평면그래프·오색정리 증명
지도를 평면 그래프(나라를 꼭짓점, 국경을 변)로 바꾸면 지도 색칠은 그래프 꼭짓점 채색 문제가 됩니다. 오일러 공식 를 이용하면 평면 그래프에는 차수가 5 이하인 꼭짓점이 반드시 존재함을 증명할 수 있습니다.
이를 바탕으로 5가지 색으로 충분하다는 오색정리는 수학적으로 쉽게 증명되지만, 4가지 색으로 줄이는 데는 100년 넘는 세월이 걸렸습니다.
다른 면에서는 다릅니다
지도가 아무리 복잡해도 이웃이 5개 이하인 작은 나라가 무조건 한 곳은 있어서 거길 공략할 수 있다
컴퓨터가 낸 첫 증명이라는 사건
1976년 아펠과 하켄은 모든 평면 지도를 1,936개의 환원 가능 배치(Reducible Configurations)로 분류하고, 슈퍼컴퓨터를 1,200시간 가동하여 사색정리를 증명했습니다.
이는 컴퓨터가 증명한 역사상 최초의 대정리로서 수학 철학계에 거대한 논쟁을 일으켰습니다. 오늘날에는 Coq과 같은 정형 검증 시스템(Formal Proof System)을 통해 완벽한 기계적 무결성이 공인되었습니다.
컴퓨터가 센 경우의 수
도넛 표면에 지도를 그리면 7개 나라가 서로 다 손을 잡을 수 있어서 색연필이 7자루나 든다
풀어 보기
그래프 채색과 오색정리 기초. 평면 그래프의 꼭짓점 채색에 대하여 다음 물음에 답하시오.
(1) 4개의 꼭짓점이 서로 모두 선분으로 연결된 완전 그래프 를 색칠하는 데 필요한 최소 색의 수를 구하시오.
(2) 꼭짓점이 5개이고 서로 모두 연결된 완전 그래프 는 평면에 변이 교차하지 않게 그릴 수 없음이 알려져 있다. 이것이 사색정리와 어떤 관련이 있는지 설명하시오.
(3) 바깥쪽에 삼각형 모양으로 3개 나라가 둘러싸고 가운데에 1개 나라가 있는 지도에서 필요한 최소 색의 수를 구하시오.
(1) 4개의 점이 모두 서로 인접하므로 4가지 색이 모두 달라야 합니다.
답과 풀이 보기
(1) 는 네 점이 서로 모두 이어져 있으므로 어느 둘도 같은 색일 수 없습니다. 따라서 4 색이 필요합니다.
(2) 는 평면에 선이 겹치지 않게 그릴 수 없습니다. 지도에서 나라들은 평면 위에 있으므로 다섯 나라가 서로 모두 맞닿는 일은 일어날 수 없습니다.
그래서 「5 색이 꼭 필요한 지도」를 만들 수가 없고, 이것이 사색정리가 참일 수 있는 바탕이 됩니다.
⛔ 다만 이것만으로 증명이 되지는 않습니다. 실제 증명은 1976 년에야 나왔고, 컴퓨터로 1,936 가지 경우를 일일이 확인해서 얻은 것이라 「사람이 손으로 확인할 수 없는 첫 증명」으로 논란이 되었습니다.
(3) 가운데 나라가 바깥 세 나라 모두와 맞닿고 바깥 셋끼리도 서로 맞닿으므로 와 같습니다 — 4 색입니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「겹치지 않게 나누기」는 색칠만의 일이 아닙니다.
- 주파수 배정 — 이웃한 기지국이 같은 주파수를 쓰면 안 됩니다. 같은 문제입니다
- 시간표 짜기 — 겹치는 수업에 같은 시간을 주지 않는 것도 색칠 문제입니다
- 도넛 위에서는 일곱 색이 필요합니다. 구멍이 뚫린 면은 사정이 다릅니다
이어지는 장
평면 지도는 네 가지 색만으로 인접한 영역을 모두 구별할 수 있지만, 도넛 모양의 토러스 곡면 위에 그린 지도는 서로 이웃하는 일곱 구역이 생겨 일곱 색이 필요해집니다 — 제116장에서 지도가 그려지는 공간의 위상적 모양에 따라 색의 수가 어떻게 달라지는지 확인해 보세요.
영감을 받은 곳
1852년 프랜시스 구스리(Francis Guthrie)가 지도를 칠하다가 제기한 추측으로, 1976년 케네스 아펠과 볼프강 하켄이 일리노이 대학의 컴퓨터를 활용하여 최초로 증명했습니다.