[호평동 영수학원] 지도는 왜 네 가지 색이면 충분할까, 4색 정리 이야기
핵심 개념
지도를 색칠할 때 규칙은 간단합니다. 국경을 맞댄 두 나라는 서로 다른 색을 써야 합니다. 바다 건너 떨어진 나라나 한 점에서만 만나는 나라는 같은 색을 써도 됩니다. 이 규칙을 지키면서 세계지도를 칠해 보면 신기한 일이 벌어집니다. 아무리 복잡하게 생긴 지도라도 색이 네 가지만 있으면 다 칠해집니다. 이것이 바로 4색 정리가 말하는 내용입니다.
이 이야기는 1852년 무렵 영국의 한 학생이 영국 지도를 색칠하다가 떠올린 질문에서 시작됐다고 전해집니다. 어떤 지도든 네 가지 색으로 충분하다는 사실을 눈치챈 그는 이를 수학자인 형과 스승에게 물었고, 이 질문이 점점 여러 수학자들에게 퍼져 나갔다고 알려져 있습니다.
언뜻 보면 당연해 보이지 않습니다. 나라가 수십 개씩 복잡하게 얽혀 있는데 색 네 개로 정말 다 칠해질까요. 직접 손으로 몇 개의 지도를 그려서 칠해 보면, 신기하게도 다섯 번째 색이 필요한 경우를 찾기가 어렵습니다.
왜 세 가지 색으로는 안 될까요. 가장 간단한 예로 네 나라가 서로 모두 국경을 맞대고 있는 상황을 생각해 보면 됩니다. 가운데에 작은 나라 하나가 있고 그 둘레를 세 나라가 고리처럼 둘러싼 지도를 그리면, 가운데 나라는 둘레의 세 나라와 모두 국경을 맞댑니다. 그러면 가운데 나라에 색 하나, 둘레 세 나라에 각각 다른 색 하나씩이 필요해서 최소 네 가지 색이 있어야 합니다.
그래서 세 가지 색으로는 부족한 지도가 분명히 있다는 것은 금방 확인됩니다. 어려운 쪽은 반대 방향입니다. 다섯 가지, 여섯 가지 색이 필요한 복잡한 지도가 있지 않을까 하는 의심을 완전히 없애는 일입니다.
이 문제가 어려웠던 이유는 지도의 모양이 무한히 다양하기 때문입니다. 나라의 개수나 국경의 생김새에 제한이 없으니, 아무리 많은 예를 손으로 확인해도 그다음에 반례가 나오지 않는다는 보장이 되지 않습니다. 수학자들은 지도를 점과 선으로 이루어진 그림으로 바꾸어 생각하는 방법을 썼습니다.
나라 하나를 점 하나로 표시하고, 국경을 맞댄 두 나라의 점을 선으로 이으면 지도는 점과 선의 그물, 즉 그래프가 됩니다. 색칠 문제는 이제 서로 선으로 이어진 두 점에 다른 색을 주는 문제로 바뀝니다. 이렇게 바꾸면 지도의 생김새와 상관없이 점과 선의 연결 구조만 다루면 되므로 문제를 다루기가 한결 쉬워집니다.
그래도 모든 경우를 다 확인하는 일은 사람 손으로 끝내기 힘들 만큼 방대했습니다. 100년이 넘게 여러 수학자가 도전했지만 완전한 증명에는 이르지 못했습니다. 1976년에 이르러 케네스 아펠과 볼프강 하켄이라는 두 수학자가 이 문제를 풀어냈다고 알려져 있는데, 그 방법이 특별했습니다.
있을 수 있는 복잡한 지도의 형태를 수백 가지 경우로 줄인 다음, 그 하나하나가 네 가지 색으로 칠해진다는 것을 컴퓨터로 확인한 것입니다. 사람이 손으로 검산하기엔 너무 많은 경우의 수였기에, 수학 역사상 처음으로 컴퓨터 계산에 크게 의존한 증명이라는 점에서 당시 수학계에 적지 않은 논쟁을 불러일으켰다고 전해집니다.
증명이 맞는지 사람이 한 줄씩 눈으로 확인할 수 없다는 사실이 많은 수학자들을 불편하게 만들었기 때문입니다.
이 논쟁은 지금까지도 완전히 사라지지 않았지만, 이후 여러 차례 다른 방식으로 검증이 이루어지면서 4색 정리는 참인 것으로 널리 받아들여지고 있습니다. 중요한 점은 이 정리가 그래프 이론이라는 분야를 크게 발전시켰다는 사실입니다. 지도, 도로망, 통신망처럼 점과 선으로 나타낼 수 있는 대상이라면 무엇이든 색칠 문제로 바꿀 수 있고, 이런 생각은 교통 신호 배정이나 통신 주파수 배분 같은 실제 문제를 다루는 데도 쓰입니다.
지도 위에 색연필로 나라를 칠하는 단순한 놀이에서 출발한 질문이 백 년 넘게 많은 수학자를 사로잡고, 끝내는 컴퓨터의 힘을 빌려야 풀리는 문제였다는 사실이 흥미롭습니다. 다음에 세계지도나 우리나라 지도를 볼 기회가 있다면, 색이 겹치지 않게 몇 가지 색으로 다 칠해지는지 한번 세어 보는 것도 재미있는 경험이 될 것입니다.