d라이브러리

4색 문제(또는 4색 정리)를 처음 제기한 사람은 1852년 당시 20대였던 프랜시스 구드리입니다. 이 문제를 동생인 프레데리크 구드리에게 알려줬고, 대학생이던 동생은 오거스터스 드모르간 교수에게 이 문제에 대해 물었습니다. 드모르간은 문제가 흥미로워 동료 수학자인 윌리엄 해밀턴에게 그 내용을 적어서 편지를 보냅니다.

1852년 10월 23일에 쓴 편지가 아직까지 남아있어 4색 정리가 어떻게 시작됐는지 정확하게 알 수 있지요.

△1852년 10월 23일, 드모르간이 해밀턴에게 보낸 편지.
편지에는 4색 문제에 대한 설명이 들어있다. 문제는 100년이
훨씬 지난 1976년 두 명의 수학자가 컴퓨터를 이용해 증명했다.
 

이 문제는 한동안 묻혀있다가 1878년 영국 수학자 아서 케일리가 영국 런던수학회 학회에서 본인도 못 푼 재미있는 문제가 있다고 소개하면서 널리 알려지게 됩니다. 이듬해 영국 수학자 알프레드 켐페가 문제를 풀었다고 발표하지요. 이후 11년 동안은 켐페가 4색 정리를 증명했다고 믿었습니다.

그런데 1890년 영국 수학자 퍼시 히우드가 증명에서 오류를 찾으면서 다시 미해결 난제가 됩니다. 이후 100년 동안 이렇다 할 진척이 없었습니다. 1976년에 이르러 두 명의 미국 수학자 케니스 아펠과 볼프강 하켄이 만약 반례가 있다면 1936가지 모양 중 하나를 반드시 포함하는데, 그 경우에도 4색이면 충분히 칠할 수 있다는 것을 컴퓨터로 증명했습니다.

△수학자들은 어떨 때 지도를 3색으로 칠할 수 있는지 연구하고 있다.
지도를 항상 3색으로 칠할 수 있는 건 아니기 때문이다.
 

4색이 가능한 건 평면그래프기 때문​
지도를 색칠하는 문제는 ‘그래프’를 색칠하는 문제로 바꿀 수 있습니다. 그래프란 꼭짓점과 두 꼭짓점을 잇는 선으로 이뤄진 구조입니다. 예를 들어 우리나라 지도에서 서울과 대전, 부산, 대구, 광주를 꼭짓점으로 하고, 서울과 대전, 대전과 광주, 대전과 대구, 대구와 부산, 광주와 대구를 선으로 이으면 그래프가 됩니다.

어떤 지도든 지도의 각 영역에 꼭짓점을 그리고 두 꼭짓점을 곡선 또는 직선으로 이어서 그래프를 만들면 평면 위에서 어느 두 선도 교차하지 않게 되는데요, 이처럼 어느 선도 교차하지 않는 평면위의 그래프를 ‘평면그래프’라고 합니다. 4색 정리는 이런 평면그래프와 관련이 있습니다.

평면그래프가 아니면 4색으로 절대 칠할 수 없는 경우가 많기 때문이에요. 예를 들어 꼭짓점이 서울과 대전, 부산, 대구, 광주고, 모든 꼭짓점을 서로 이어 선이 총 10개가 있다면 이 5개의 꼭짓점은 4색으로 칠할 수 없습니다. 5색이 필요하지요. 평면그래프라는 조건 덕분에 색의 수를 4가지로 줄일 수 있었던 겁니다.
 

4색에서 3색으로 줄일 해법은?
그렇다면 조건을 더 붙여서 필요한 색의 수를 더 줄일 수는 없을까요? 많은 수학자가 이 물음에 대해 연구해 왔습니다. 그 대표적인 예가 1959년 독일 수학자 헤르베르트 그뢰치가 발표한 ‘그뢰치의 정리’입니다. 삼각형이 없는 평면그래프는 3색으로도 칠할 수 있다고 밝힌 겁니다.

4색 정리는 증명 과정이 너무 길어서 다 읽고 확인한 사람이 없습니다. 증명이 맞는지도 컴퓨터가 따졌지요. 2005년 마이크로소프트 연구소에 근무하는 조지 공티에 박사가 컴퓨터가 4색 정리의 증명을 읽을 수 있도록 바꿨고, 컴퓨터가 증명이 옳다고 확인해줬습니다. 반면, 그뢰치의 정리는 사람이 확인할 수 있을 만큼 간단합니다.

2009년 체코 수학자 즈데네크 드보르자크와 로빈 트호마스, 다니엘 크랄은 그뢰치의 정리를 일반화한 문제를 풀었습니다. 즉 ‘삼각형이 있더라도 삼각형끼리의 거리가 매우 멀면 그 평면그래프는 3색으로 칠할 수 있다’는 것을 증명했습니다.

증명에는 10100 정도로 매우 큰 상수가 등장하는데요. 삼각형끼리 거리가 이 상수 정도로 멀면 된다는 겁니다. 그런데 10100이라는 큰 수가 실제로 필요할까요? 더 작은 수면 안 될까요? 수학자들은 현재 최적의 거리가 4 이상 10100 이하라는 것만 알고 있어요. 최적의 값을 구하는 문제 역시 미해결 문제입니다.

스타인버그의 추측은 틀렸다!
이제 이번 달 주제인 스타인버그의 추측에 대해 이야기해보겠습니다. 1976년 캐나다 수학자 리차드 스타인버그는 ‘사각형과 오각형이 없는 평면 그래프는 3색으로 칠할 수 있다’고 추측했습니다. 1991년 헝가리 수학자 에르되시 팔은 이 문제의 조건을 약하게 바꿔 다음과 같이 생각했습니다. ‘사각형과 오각형, …, k각형이 모두 없는 임의의 평면그래프는 3색으로 칠해진다고 할 때 가능한 최소의 k값이 무엇일까?’ 이후 수학자들은 스타인버그 추측과 에르되시의 물음을 해결하기 위해 노력했습니다.

 

 

※ 엄상일 교수는 KAIST 수학과를 졸업하고, 미국 프린스턴대에서 박사 학위를 받았습니다. 현재는 KAIST에서 강의와 연구를 하고 있습니다. 그래프이론과 이산수학, 조합적 최적화가 주요 연구 분야입니다. 2012년에는 젊은과학자상(대통령상)을 수상했고, 2013년에는 한림선도과학자로 선정됐습니다.