d라이브러리

여러분은 안 풀리는 문제를 풀 때 어떻게 하나요? 수학자는 여러 각도로 문제를 생각해봅니다. 때로는 문제를 더 어렵게 바꿔보는데요, 그게 오히려 문제를 쉽게 해결하게 만들기도 하고 새로운 연구 주제를 탄생시키기 때문입니다. 이번 호에 소개할 ‘하트비거의 추측’ 역시 4색 문제를 어렵게 만들다 나왔습니다.

그래프 이론에서 가장 유명한 문제를 꼽자면 단연 ‘4색 문제’입니다. 4색 문제는 평면에 그린 지도에서 이웃한 나라의 색을 다르게 칠할 때 나라가 아무리 많아도 4색만 있으면 된다는 걸 증명하는 문제입니다. 

1852년 영국의 대학생이던 프랜시스 구드리가 처음 질문한 이래로 많은 수학자가 도전했고, 1970년대에 미국 일리노이대학교의 두 교수 케네스 아펠과 볼프강 하켄이 해결했습니다. 

하지만 아직 컴퓨터를 사용한 증명만 있어서 컴퓨터를 쓰지 않은 증명을 고민하는 수학자가 많습니다. 4색 문제처럼 어려운 문제를 풀기 위해서 수학자는 다양한 방법으로 고민합니다. 특히 원래 문제를 변형해 더 어렵고 추상적인 문제로 만들어서 생각하는 것을 즐깁니다. 군더더기를 제외하고 문제의 핵심만 남겨 일반화해 더 어려운 상황을 만들면 그 덕분에 문제가 해결되는 경우가 있기 때문이죠. 많은 경우 이런 과정을 거치다가 새로운 수학 연구 주제가 생깁니다.

4색 문제 풀다 탄생한 하트비거의 추측

4색 문제가 풀리기 전인 1943년 스위스의 수학자 휴고 하트비거 역시 4색 문제를 어떻게 하면 더 일반화할 수 있을지 고민했습니다. 그 과정에서 ‘하트비거의 추측’도 나왔죠. 이번 호에서는 하트비거의 추측을 먼저 설명하고, 이 추측에 어떤 새로운 소식이 있는지 전하고자 합니다.

4색 문제는 그래프에 관한 문제로 바꿀 수 있습니다. 그래프란 꼭짓점과 두 꼭짓점을 잇는 선으로 구성된 수학적 대상입니다. 꼭짓점의 집합 V와 V의 원소 두 개로 구성한 선을 모아놓은 집합 E의 순서쌍 (V, E)로 정의합니다. 

지도의 각 나라마다 꼭짓점을 그리고, 두 나라가 국경을 맞대고 있으면 두 꼭짓점 사이에 선을 연결해서 그래프를 그릴 수 있습니다. 이때 선을 잘 그리면 서로 다른 두 선이 서로 교차하지 않게 지도에 나타낼 수 있습니다. 이처럼 서로 다른 두 선이 교차하지 않도록 평면에 그릴 수 있는 그래프를 ‘평면 그래프’라고 부릅니다.

이제 4색 문제를 그래프의 언어로 바꿔봅시다. 원래는 나라에 색칠했지만, 이제는 그래프의 꼭짓점에 색칠합니다. 이웃한 나라는 다른 색이므로, 선으로 연결한 두 꼭짓점도 다른 색이어야 합니다. 이렇게 바꾸면 이 문제는 그래프의 꼭짓점을 칠하는 채색 문제가 됩니다. 선으로 연결한 두 꼭짓점끼리는 다른 색이 되도록 색을 칠할 때 필요한 색의 수의 최솟값을 그 그래프의 ‘채색수’라고 부릅니다. 

참에 더 가까워진 하트비거의 추측!

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

참고자료

세르게이 노린, 쑹쯔샤 ‘Breaking the degeneracy
barrier for coloring graphs with no Kt minor’, 영문 위키백과 ‘하트비거 추측’