사색정리 (Four Color Theorem)

한 줄 정의: 평면 지도의 인접한 나라를 네 가지 색으로 모두 구분해 칠할 수 있다는 정리입니다.

쉽게 풀면

지도를 칠할 때 국경을 맞댄 두 나라가 같은 색이 되지 않도록 하려면 몇 가지 색이 필요할까요. 답은 네 가지면 충분하다는 것입니다. 아무리 복잡하게 생긴 지도라도 네 색을 넘길 필요가 없으며, 세 색으로는 부족한 지도가 존재하므로 네 가지가 최선입니다.

왜 중요한가

150년 가까이 미해결이던 문제가 1976년 컴퓨터를 이용해 해결되면서, 컴퓨터 보조 증명을 수학적 증명으로 인정할 것인가라는 논쟁을 촉발한 상징적 사례입니다. 그래프 색칠 이론의 출발점으로서 일정 배정, 주파수 할당, 레지스터 할당 문제와도 연결됩니다.

논문에서는 이렇게 쓰입니다

"인접 관계를 평면 그래프로 모형화한 뒤 사색정리에 근거하여 네 개의 그룹으로 분할하였다."

조금 더 깊게 보면

지도의 각 나라를 정점으로, 국경을 맞댄 관계를 변으로 바꾸면 평면 그래프의 색칠 문제가 됩니다. 아펠과 하켄의 증명은 반례가 존재한다면 반드시 포함해야 하는 구성들의 유한 목록을 만들고, 각 경우를 컴퓨터로 확인하는 방식이었습니다. 다섯 가지 색이면 충분하다는 오색정리는 훨씬 간단히 손으로 증명되며, 곡면의 종수가 커지면 필요한 색의 수도 늘어납니다.

주의할 점

나라가 하나로 이어져 있어야 한다는 전제가 있어서, 본토와 떨어진 영토를 같은 색으로 칠해야 하는 실제 지도에는 그대로 적용되지 않습니다. 또 이 정리는 색칠 방법을 효율적으로 찾아 주는 알고리즘을 뜻하지 않습니다.