오색 정리

진술

오색 정리(Five color theorem)은 임의의 평면그래프를 다섯 가지 색을 이용하여 칠할 수 있다는 명제다. 다시 말해, 평면그래프 G의 색의 개수를 [math]\displaystyle{ \chi(G) }[/math]라 하면,

[math]\displaystyle{ \chi(G)\le 5 }[/math]

이다.

평면그래프의 색의 개수와 관련해 현재 닝겐 혼자 힘으로 도달할 수 있는 가장 강력한 결론이다.

증명

[math]\displaystyle{ \deg v \le 4 }[/math]이면 v에는 언제나 인접한 꼭지점과 다른 색을 칠하면 된다.

그래프의 모서리의 수 v에 대한 수학적 귀납법으로 증명하려고 한다.

• 기본 단계: [math]\displaystyle{ v=1 }[/math]이면 평면그래프를 한 가지 색을 이용하여 칠할 수 있다.
• 귀납법 단계: [math]\displaystyle{ v=n-1 }[/math]인 평면그래프를 다섯 가지 색을 이용하여 칠할 수 있다고 가정하자. [math]\displaystyle{ v=n }[/math]일 때, 평면그래프 G는 차수가 5 이하인 꼭지점을 반드시 하나 가진다. 이 꼭지점을 x라 하자. G에서 x를 제거한 그래프 G' 의 꼭짓점은 n-1개이므로, G' 는 다섯 가지 색을 이용하여 칠할 수 있다. 따라서 G를 다섯 개 색으로 칠할 수 있음을 보이려면 x를 잘 색칠하면 된다.
  • [math]\displaystyle{ \deg x \le 4 }[/math]일 때, v와 인접한 꼭짓점의 색은 최대 네 가지에 불과하므로, 인접한 꼭짓점의 색이 아닌 걸 적당히 골라서 x에 색칠하면 된다.
  • [math]\displaystyle{ \deg x =5 }[/math]라고 하자. 이때, x와 인접한 꼭짓점을 시계방향으로 [math]\displaystyle{ v_1,v_2,v_3,v_4,v_5 }[/math]로 지정하고, 색을 1, 2, 3, 4, 5로 부여하자. G' 의 부분그래프 [math]\displaystyle{ G_{1,3} }[/math]을 G' 에서 색이 1과 3인 것을 모두 고르고 모서리로 연결한 그래프라고 하자. 이때 [math]\displaystyle{ G_{1,3} }[/math]에서 v₁에서 v₃로 가는 길이 없다면, v₁의 색을 v₃의 색으로 바꾸고 v₁과 연결된 점의 색 1, 3을 서로 바꾸면 된다. 그리고 x를 1로 칠하면 된다.

음... [math]\displaystyle{ v_2,v_4 }[/math]를 다른 모서리에 닿지 않고 연결하려면 지면을 뚫으면 되겠군그런 거 없다.

[math]\displaystyle{ G_{1,3} }[/math]에서 v₁에서 v₃로 가는 길이 있다고 하자. 그러면 이제 얘 말고 G' 에서 색이 2와 4인 것을 모두 고르고 모서리로 연결한 그래프인 [math]\displaystyle{ G_{2,4} }[/math]에 대해 생각하자. [math]\displaystyle{ G_{2,4} }[/math]에서 v₂에서 v₄로 가는 길이 없다면 [math]\displaystyle{ G_{1,3} }[/math]의 경우처럼 색을 바꾸면 되는데, v₂에서 v₄로 가는 길이 있다면 G가 평면그래프라는 것에 모순이다! 따라서 [math]\displaystyle{ G_{2,4} }[/math]에서 v₂에서 v₄로 가는 길은 없다. 따라서 G를 다섯 가지 색으로 칠할 수 있으므로 언제나 원하는 결론을 얻는다.

같이 보기

• 사색 정리: 오색 정리보다 강력한 정리로, 임의의 평면그래프는 네 가지 색을 이용해 칠할 수 있다. 1976년에 컴퓨터를 이용해 증명하였다.

외부 링크

• Five Color Theorem. (2014, August 13). ProofWiki, . Retrieved 14:39, May 5, 2015.
• Mapa kodów pocztowych - Polska: 폴란드 구역을 다섯 가지 색으로 칠해 보여준다. 2015년 9월 12일 확인.