'4색 정리', 4가지 색으로 어떤 지도든 서로 다른 색으로 칠할 수 있다?

 

 

'4색 정리',

4가지 색으로 어떤 지도든 서로 다른 색으로 칠할 수 있다?

 

▲ 4가지 색으로 모든 지도를 칠할 수 있다?

 

여러분은 혹시, 4가지 색만 가지고 이 세상의 어떤 지도든 같은 색이 인접하지 않게 칠할 수 있다는 사실을 아시나요? 오늘은, 일명 ‘4색 문제’라 불렸던 이 난제와 이를 해결하기 위해 힘써 왔던 많은 과학자와 수학자를 만나보려 합니다.

 

 

과연 ‘4색 정리’란 무엇일까요?

프란시스 거스리 (Francis Guthrie, 1831-1899)는 어느 날 영국의 지도를 색칠하던 중 서로 다른 4가지의 색으로 모두 칠할 수 있다는 것을 발견하게 됩니다. 이를 들은 그의 동생은, 드모르간 법칙 등을 창시한 당시 수학자로 유명했던 오거스터스 드모르간(Augustus De Morgan, 1806-1871)에게 ‘네가지 색으로 모든 지도를 칠하는 것’에 관해 질문하게 되고, 이후 이 문제를 ‘4색 문제’라고 부르게 됩니다. ‘4색 정리’는 바로 이 ‘4색 문제’를 증명한 것입니다.

 

▲ 4색 정리의 증명에 첫 발은 내딛은 알프레드 캠프와 퍼시 히우드

 

이 문제가 세간에 알려진 후, 수많은 수학자들이 증명하려고 노력했지만, 최초의 ‘그럴 듯 한’ 증명은 1879년 알프레드 캠프 (Alfred Kempe, 1849-1922)에 의해 처음으로 제시됩니다. 하지만 11년 후, 그의 증명에도 조금의 문제가 있음이 밝혀지고, 이후 비슷한 증명이 모두 틀렸음이 드러나며, 증명은 다시 원점으로 돌아가게 됩니다. 하지만 캠프의 노력이 완전히 휴지 조각이 돼 버린 것은 아니었는데요, 퍼시 히우드 (Percy Heawood, 1861-1955)는 캠프의 증명을 손질해서 5가지 색으로 모든 지도를 칠할 수 있음을 증명할 수 있다는 것을 발견합니다.

 

​

▲ 곡면(원환면)의 다양한 종류들

 

히우드는 캠프의 아이디어를 평면 지도가 아닌 곡면에 적용할 수 있음을 알아냅니다. 여기서 이야기하는 곡면은 흔히 우리가 볼 수 있는 도넛 모양 등을 의미하는데요, 이 곡면들의 겉면이나, 정육면체의 겉면이나, 서로 연결된 상태가 같으므로 채색 문제에서는 굳이 구별할 필요가 없게 됩니다. 즉 곡면 위에 그린 지도와 정육면체의 겉면에 그린 지도를 구분할 필요가 없다는 것입니다.

 

▲ 오일러 표수 등 수학계에 큰 업적을 남긴 레온하르트 오일러,

그는 말년에 눈이 불편하였지만 수학에 대한 열정은 식지 않았다고 한다.

 

히우드가 색을 칠하는 방법의 수를 예측할 때 사용한 것은 바로 ‘오일러 표수’입니다. 오일러 표수는 입체도형의 꼭짓점, 모서리, 면의 개수의 관계를 나타는데요. 곡면에 지도를 그린 뒤, 꼭짓점의 개수를 V, 모서리의 개수를 E, 면의 개수를 F라고 한다면, V-E+F값을 그 곡면의 ‘오일러 표수’라고 합니다.

 

▲ 평면에 그린 삼각형과 구체인 축구공, 이 둘의 오일러 표수 값은 같다.

 

이를테면 평면에 삼각형을 그리면 꼭짓점 3개, 모서리 3개, 면은 2개 (삼각형의 바깥 부분도 하나의 면으로 여깁니다.) 이므로 이를 계산하면 값은 2가 됩니다. 그리고 신기하게도, 둥근 축구공(구체)의 꼭짓점, 모서리, 면의 개수를 계산한 값도 2가 됩니다.

 

▲ 곡면에 한 개의 구멍이 뚤린 도넛 모양의 원환면

 

​

오일러 표수의 값은 곡면에 구멍이 하나 늘어날수록 (이를테면 도넛처럼) 값이 2만큼 감소한다는 것이 알려져 있는데요, 이를 통해 구체 등을 제외한 대부분의 곡면의 오일러 표수 값은 음수임을 생각할 수 있습니다. 히우드는 이 표수를 응용해 ‘오일러 표수의 값이 0과 같거나 작은’, 즉 대부분의 곡면 위에 그린 지도는 7가지 색만으로 칠할 수 있음을 예측하고, 1968년 게르하르트 링겔과 존 영스라는 수학자 둘에 의해, 클라인 병 모양에서를 제외하고는 히우드의 예측이 옳다는 것이 증명됩니다.

 

하지만 평면에서는 오일러 표수의 값이 양수가 나오기 때문에, 히우드의 증명법을 사용할 수가 없었습니다.

 

 

  

▲ 4색 정리가 증명된 70년대에 사용되던 컴퓨터의 모습 (사진 출처 : CC, Ben Franske)

 

이렇게 꾸준히 연구되던 4색 정리는 1970년대 와서 그 증명을 완성하게 됩니다. 이는 최초의 컴퓨터를 이용한 수학 증명으로도 유명하죠. 하인리히 헤슈 (Heinrich Heesch, 1906-1995)는 ‘무한대 방을 가진 호텔’ 이야기로 유명한 힐베르트의 제자 중 한 명이었습니다. 대학에서 ‘그래프 이론’을 연구하던 헤슈는 4색 문제를 컴퓨터로 증명할 수 있겠다는 생각을 하고, 여러 학자들과 함께 아이디어를 공유합니다. 하지만 그의 조국이었던 독일이 재정적인 압박으로 연구 자금 제공을 중단하게 되고, 결국 증명의 영예는 1976년 6월, 1,000여 시간의 컴퓨터 계산 끝에 증명을 끝마친, 미국의 일리노이 대학교의 캐네스 아펠 (Kenneth Appel, 1932-2013)과 볼프강 하켄 (Wolfgan Haken, 1928-)에게 돌아가게 됩니다.

 

평면에 그릴 수 있는 지도는 무한개이지만, 이를 일일이 다 칠해본다는 것은 아무리 컴퓨터라 할 지라도 말이 되지 않습니다. 헤슈는 캠프의 아이디어에서 컴퓨터가 칠해야 할 지도들의 개수를 줄이는 방법을 고안해 냅니다. 그는 지도의 가운데 꼭짓점 부분을 확장시켜 (가운데 부분을 확장시켜 인접한 면마다 모서리를 하나씩 더 만들어 주는 방식), 한 꼭짓점에 모서리가 세 개 이상 모이면 모든 꼭짓점마다 모서리가 세 개인 지도로 바꿀 수 있고, 이 지도가 4가지 색으로 칠해질 수 있음을 증명합니다.

 

 

▲ 지도를 변형해 증명할 후보군을 줄여 나가는 방식 (사진 출처 : 네이버)

 

즉, 인접한 면의 개수가 3개인 곳이 하나라도 있는 지도는 꼭짓점을 변형하여 4가지 색으로 칠할 수 있고, 이를 축소 가능하다고 합니다. 오일러 표수를 이용하면, 지도의 종류는 인접한 면의 개수가 3개, 4개(한 쪽이 뚫린 육면체 모양), 5개인 영역이 반드시 하나는 있음을 증명할 수 있습니다. 헤슈는 인접한 면의 개수가 3개, 4개일 때 축소 가능함을 증명하였고, 이제 5개일 때만 증명하면 4색 정리의 증명은 끝납니다!

 

아펠과 하켄은 이를 통해 색칠할 후보들의 수를 줄여 직접 컴퓨터로 칠해 보고자 했습니다. 처음에는 그 지도의 개수가 약 만 개 정도 되었지만, 그들은 후보를 2천 개 정도까지 줄여 이를 컴퓨터에 입력합니다. 약 50여일 후, 487가지의 판별 규칙을 통해 검사하던 컴퓨터는 그들이 입력한 후보군 1,936개의 지도가 모두 축소 가능함을 보였고, 4색 정리는 컴퓨터를 통해 증명되게 됩니다. 이는 당시 ‘인간이 검증할 수 없는’ 증명이라며 크게 논란이 되었지만, 요즘에는 컴퓨터가 증명에 성공했다는 것을 인정한답니다.

 

 

 

참고문헌 :

한번 읽고 평생 써먹는 수학 상식 이야기 (정경훈)

페르마의 마지막 정리 (사이먼 싱)

 

2017 교육부 블로그 기자단 /​ 이승빈

​

​

​

​

​

​

​