지도에서 이웃한 나라를 다른 색으로 칠하려면 몇 가지 색이 필요할까? 1852년에 제기된 이 질문은 ‘4가지면 충분하다’는 사색정리로, 1976년 컴퓨터를 이용해 처음 증명되었다. 시험 시간표 짜기, 주파수 배정이 모두 그래프 색칠 문제이다.
핵심 개념
- 꼭짓점 색칠: 변으로 연결된 두 꼭짓점이 다른 색이 되도록 칠하는 것
- 채색수 $\chi(G)$: 필요한 최소 색의 수. $\chi(K_n)=n$, 짝수 길이 회로는 $2$, 홀수 길이 회로는 $3$
- 평면 그래프: 변이 교차하지 않게 평면에 그릴 수 있는 그래프. 지도의 나라를 꼭짓점, 국경을 변으로 하면 평면 그래프가 된다.
- 오일러 공식: 연결 평면 그래프에서 $V-E+F=2$ ($F$는 바깥 영역을 포함한 면의 수)
핵심 정리
- 오일러 공식 $V-E+F=2$
- 단순 평면 그래프는 $E\le3V-6$이고, 차수가 $5$ 이하인 꼭짓점이 있다.
- 오색정리: 모든 평면 그래프는 $5$가지 색으로 칠할 수 있다. (사색정리: $4$가지로 충분하다)
증명 보기
오일러 공식. 변의 수에 대한 귀납법. 트리이면 $E=V-1$, $F=1$이므로 $V-(V-1)+1=2$이다. 회로가 있으면 회로 위의 변 하나를 지운다. 그 변은 두 면의 경계이므로 지우면 두 면이 합쳐져 $E$와 $F$가 하나씩 줄고 $V-E+F$는 그대로이다.
$E\le3V-6$. ($V\ge3$) 각 면은 적어도 $3$개의 변으로 둘러싸이고 각 변은 많아야 두 면의 경계이므로 $3F\le2E$이다. 오일러 공식에 넣으면 $2=V-E+F\le V-E+\frac23E$, 즉 $E\le3V-6$이다. 차수의 합 $2E\le6V-12$이므로 평균 차수가 $6$보다 작고, 따라서 차수가 $5$ 이하인 꼭짓점이 있다.
오색정리 (생각의 흐름). 꼭짓점 수에 대한 귀납법. 차수가 $5$ 이하인 꼭짓점 $v$를 지운 그래프를 $5$색으로 칠한다. $v$의 이웃이 $4$색 이하를 쓰면 남는 색으로 $v$를 칠한다. 이웃 $5$개가 모두 다른 색이면, 두 색만으로 이루어진 경로의 색을 서로 바꾸는 ‘켐페 사슬’ 논법으로 한 색을 비울 수 있다(평면성 때문에 두 사슬이 동시에 막힐 수 없다). $\blacksquare$
예제
- 정육면체: $V=8$, $E=12$, $F=6$, $8-12+6=2$
- $K_5$는 평면 그래프가 아니다: $V=5$이면 $E\le9$인데 $K_5$는 $E=10$이다.
- 시험 시간표: 과목을 꼭짓점으로, 같은 학생이 듣는 과목을 변으로 이으면, 채색수가 필요한 최소 시간대의 수이다.
확인 문제
모든 면이 오각형이고 각 꼭짓점에서 세 면이 만나는 볼록 다면체의 면은 몇 개인가?
풀이 보기
면이 $F$개이면 $E=\frac{5F}{2}$, $V=\frac{5F}{3}$이다. 오일러 공식에 넣으면 $\frac{5F}3-\frac{5F}2+F=2$, $\frac{F}{6}=2$, $F=12$이다. (정십이면체)
정리
- 평면 그래프: $V-E+F=2$, $E\le3V-6$
- 평면 지도는 4색으로 충분하다 (사색정리).
