Page 9 - 송도고등학교 수학일보 제5호

SONGDO HIGH SCHOOL 09

컴퓨터를 이용한 최초의 증명, 4색 정리

4색 정리 또는 4색 문제는 평면을 유한개의 부분으로 나누어 각 컴퓨터를 처음으로 컴퓨터를 이용해 이를 증명하려는 생각을 하였

부분에 색을 칠할 때, 서로 맞닿은 부분을 다른 색으로 칠한다면 네 으나 자금 부족으로 실패하였고, 미국의 볼프강 하켄, 케네스 아펠
가지 색으로 충분하다는 정리이다. 이 문제는 지도에서 서로 맞닿 이 그의 아이디어를 바탕으로 컴퓨터 두 대를 약 50여일 1200시

은 지역에 다른 색을 칠한다는 것에서 착안해 만들어졌다. 앞선 시 간 동안, 487가지의 판별 규칙을 통해 가동시킨 끝에 증명에 성공
기에 독일의 수학자 뫼비우스가 4색 문제를 먼저 거론했다는 기록 하였다. 이들은 컴퓨터를 이용해 가능한 모든 경우의 지도 모델을

이 있긴 하지만, 이 문제가 본격적으로 알려진 계기는 영국의 수학 뽑아 4색 정리를 적용해 보았을 때 반례가 나오지 않는다는 결과
자 드모르간이라는 것이 정설이다. 1852년 영국의 식물학자 프란 를 바탕으로 4색 정리를 증명하는데 성공하였다. 많은 수학자들은

시스 구스리(Fransis Guthrie)는 영국 지도를 구획 별로 색칠하던 이 증명은 수학의 본질을 해치며 '인간이 검증할 수 없는 증명은 받
중 4가지 색만 있으면 인접한 지역끼리 서로 겹치지 않게 칠할 수 아들일 수 없다'라고 말하며 거부하는 움직임을 보였지만, 위상수

있다는 것을 깨닫고는, 다른 모든 지도의 경우에도 그러한지 궁금 학과 그래프 이론을 발전시켰으며, 최초로 컴퓨터를 이용해 증명한
해했다. 프란시스의 동생 프레드릭은 형에게 들은 지도와 4가지 색 난제로 이후 수학적 증명 과정에서의 컴퓨터 사용을 활성화시켰다

에 대한 이야기를 저명한 수학자 오거스터스 드 모르간에게 물었는 는 점에서 의미가 깊은 증명이기도 하다.
데, 이후 드모르간 본인을 포함하여 수많은 수학자들이 4색 문제에

뛰어들었다. 다른 난제들과 달리 어린아이도 이해할 수 있는 간단 (NOM 1학년 김희원 기자)
한 문제라서, 별 거 아닐거라 여러 사람들이 자신만만하게 증명을

시도했다가 낭패를 보는 일이 많았다. 특히 수학자 중엔 반평생동
안 이 문제에만 매달렸으나 이 난제를 해결하지 못하는 경우가 많

았다. 4색 문제를 자신이 해결했다는 사람은 많았으나 대부분은 엉
터리였고, 수학자들조차도 한동안 부분적, 간접적 증명에서 더 이

상 발을 떼지 못했다. 1879년 알프레드 켐프(Alfred Kempe)가
증명을 내놓으면서 4색 문제에 종지부를 찍는 듯 보였지만 11년

뒤에 증명 과정의 오류가 밝혀지며 다시 원점으로 돌아오는 일도
있었다. 이 오류를 밝힌 퍼시 히우드(Percy Heawood)는 켐프의

정리를 손질하여 5색으로는 어떠한 지도라도 색칠이 가능하다는 5
색 정리를 증명하는 데 성공한다. 1960년대 독일의 수학자 헤쉬는