시작하기 전에 : 이제부터 추가되는 많은 용어들은 영어 그대로 사용핧 것입니다. 제가 4색문제에 사용된 영어 용어들의 한글번역을 모르기 때문이기도 한데, 그보다는.. 직접 예를 들어 보지요. 뒤에 가면 이런 종류의 논의가 튀어나올 겁니다.
“....그들이 발견한 graph configuration들의 집합의 unavoidability는 discharging procedure를 통해서 증명할 수 있다. ”
이걸 한글로 바꾼다면 (번역된 용어를 모르기 때문에 직접 번역했습니다.)
“.... 그들이 발견한 그래프 형상들의 배제불가능성은 방전 절차를 통해서 증명할 수 있다.”
한글로 읽힌다는 사실 외에는 이해하는데 도움이 되지 않음을 느끼실 수 있을 겁니다. 왜냐면 이것들은 우리가 일상에서 쓰는 단어의 그 의미로써 쓰이고 있지 않거든요. 대체 ‘배제불가능성’ 이 뭘까요? 이건 누군가가 정의해놓은 뜻을 보기 전까지는, 추측만 할 수 있을 뿐 알 수 없습니다. 저는 앞으로 이런 새 용어들을 전부 설명할 겁니다. 그런데 단어 뜻을 전부 설명한다면, 그 단어가 영어이냐 한글이냐는 별 상관이 없겠지요. “~~ 한 상태를 A라고 한다.” 랑, “~~한 상태를 갑이라고 한다.” 랑의 차이를 보세요.
자. 그러면 지금의 상황을 이해해주시리라 믿고.. 계속 진행해 봅시다.
지난화에서 최대 평면 그래프 maximal planar graph 인 4색문제의 반례는 반드시 차수 5 이하인 점을 갖는다는 것을 알아냈습니다. 그때 말했던 것처럼, 이것과 모순되는 사실을 찾아내려고 합니다. 이와 모순을 찾아내기 위해서는 간단하게 위의 명제의 부정을 생각해보면 됩니다.
주어진 명제는
“최대평면 그래프 maximal planar graph 인 반례에는 반드시 차수degree가 5 이하인 점이 존재한다.”
이므로, 이것의 부정은
“어떤 maximal planra인 반례에는 차수가 5 이하인 점이 하나도 없다.”
가 되죠. 이제 그게 “어떤‘ 그래프인지를 찾아보면 됩니다.
1. minimal counterexample
그래프를 파는 쇼핑몰이 있다고 합시다. 4색문제의 반례를 찾으면, 앞에서 알아본 것과 같이 반드시 하나 이상이 검색되겠죠?
검색결과를 점갯수 오름차순 정렬을 합니다.
그러면 점갯수가 제일 작은 것부터 검색결과에 나올 겁니다.
이렇게 점갯수가 제일 작은 걸 이제부터 최소반례 minimal counterexample 라고 합시다. minimal counterexample의 특징은 그 정의에서 볼 수 있듯이 .. 그것들이 제일 작다는 사실입니다. 제일 작다는게 무슨 말이냐면, 이것들에서 점을 하나만 빼 본다면, 더이상 반례가 아니라는 말입니다. 그건 당연하죠. 방금 우리가 최저가 최저 점갯수인 것을 선택했으니까, 그것보다 작은 반례는 없을 테니까요.
이렇게 점갯수가 최소인 것들 중에 maximal planar 인 반례는 반드시 있습니다. 이건 당연하죠. 점갯수가 최소인 반례에서 선을 있는대로 집어넣으면 그게 maximal planar graph니까요. 그리고 이게 우리가 앞으로 관심갖게 될 녀석입니다.
maximal planar graph인 minimal counterexample.(아까 그 검색에 나온 첫번째 그래프.)
자. 이제, “ 차수가 1,2,3,4 인 점이 하나도 없”는 녀석을 찾아냈습니다.
1.a 이녀석이 차수3인 점을 안 가지는 이유
귀류법으로 알아낼 수 있습니다. 차수 3인 점이 있다고 칩시다.
당연히 선의 끝에는 서로 다른 점들이 있겠죠.
그리고 이 점들은 서로 연결되어 있겠지요. (우리가 현재 다루고 있는 반레는 maximal planar입니다. 만약 이 점들이 직접 연결되어 있지 않다면, 선을 더 그을수가 있어요.즉 maximal planar가 아니게 돼요.)
가운데 점을 하나 뺍니다. minimal counterexample이었으므로, 이렇게 빼면 더이상 반례까 아닙니다. 즉, 네 가지 색으로 칠할 수 있습니다.
물론 우리가 지금 이 바깥의 모양을 알고 있는건 아닙니다. 그러나 너무 당연한 이유로 지금 그림에 있는 세 점은 칠할 수 있습니다.
삼각형의 꼭지점들은 서로 연결되어 있으니까요. 서로 다른 색으로 칠해질 수밖에 없습니다.
그런데, 이건 말이 안됩니다. 아까 뺀 점을 다시 추가해보세요. 그러면 그래프는 아까의 반례가 되지만
삼각형 꼭지점 위에서 쓰이지 않은 네 번째 색을 여기에 칠하면..
자. 이제 4가지 색만으로 반례를 칠했습니다. 이건 불가능하죠. 반례의 정의가 4가지 색으로 못 칠하는 그래프니까요. 귀류법에 의하여, 여기에 차수 3인 점은 없습니다. ///
완전히 같은 방법으로 차수 1.2 인 점도 없음을 보일 수 있습니다.
1.b. 이녀석이 차수 4인 점을 안 가지는 이유
차수 4일 때는 더이상 위의 테크닉을 사용할 수 없습니다. 왜냐면 각 꼭지점에 모두 다른 색이 칠해지면, 4가지 색을 다 써버리잖아요.
가운데 점을 빼서 나머지 부분을 4색으로 다 칠하고. 점을 다시 추가했을 때, 다섯번째 색이 필요할 수도 있죠. 물론, 사각형의 꼭지점을 두가지 색이나 세가지 색만으로 색칠된다면 또 모를까. 음..좀 헷갈리네요. 차근차근 써 보도록 합시다.
차수 4인 점이 있다고 하자. 앞의 과정과 똑같이 가운데 점을 빼면, 4색으로 그래프를 색칠할 수 있다.
case 1. 만약, 가운데 점을 뺀 그래프를 4가지 색으로 색칠했을 때, 사각형의 꼭지점 네 개가 오직 두 가지 색만으로 칠해진다면
즉 이런 경우, 다시 점을 추가해도 색의 추가 없이 가운데 점을 색칠할 수 있으므로,(파란색이나 초록색을 칠하면 되죠.) 앞의 삼각형일 때와 같은 이유로 모순이다. 따라서 이 케이스가 일어나는건 불가능하다.
case 2. 사각형의 꼭지점이 세 가지 색으로 칠해진다면
이때도 역시 다시 점을 추가해도 색이 추가되지 않으므로, 이 케이스도 불가능하다.
마지막 case 3. 사각형의 꼭지점이 모두 다른 색으로 칠해진다면
자. 이 부분이 재미있는 부분인데, 이것의 해결방법은 (우리가 지금 하고 있는 이 과정을 처음 발견한 Alfred Kempe의 이름을 딴) Kempe chain 을 이용합니다.
Kempe chain이란 색칠된 그래프 위에서 특정한 두 색이 번갈아가며 반복되는 고리를 말합니다. 이 역시 그냥 예를 보는게 이해가 빠른데..
이 그래프를 살펴보면, 파랑-노랑 Kempe chain은
이렇게 한개가 있고, 빨강-노랑 Kempe chain은
이렇게 2개가 있음을 알 수 있습니다.
원래 문제로 돌아와서... 사각형의 꼭지점마다 다른 색이 칠해져 있을 때.. 마주 보는 두 꼭지점이 가지고 있는 두 색을 선택합시다.
즉 여기서 빨강-노랑을 선택하거나, 파랑-초록을 선택합니다. 우리는 빨강-노랑을 선택해 봅시다. 빨강과 노랑에서부터 시작하여, 빨강-노랑 Kempe chain을 최대한으로 연장해 봅시다.
subcase 3-1.
만약 chain이 연결되지 않는다면, 이런 식으로 그려지겠지요.
이들 주변의 모든 점은 파랑과 초록으로만 이루어져 있습니다. 따라서 빨강과 노랑의 색을 서로 맞바꾸어도, 마주하는 나라가 같은 색을 가지게 될 일은 없습니다.
이렇게 한 쪽의 chain의 색을 뒤바꾸면, 어떤가요? 사각형 위에는 단 3개의 색만이 놓이게 됩니다. 이 상태로 다시 가운데에 점을 추가하고, 사용하지 않은 색 (이 경우에는 빨간색) 을 추가하면, 4가지 색으로 반례를 칠해버린 게 되죠. 이건 모순이니 이 케이스도 불가능합니다.
마지막 subcase 3-2.
chain이 연결된다면, 앞에서와 같이 빨강-노랑의 색을 뒤바꿔도 사각형 위에는 여전히 4가지 색이 놓이게 됩니다.
그런데 이런 상황이라면, 파랑-초록 Kempe chain은 연결될수가 없죠. 빨강-노랑 Kempe chain이 둘 사이를 갈라놓고 있으니까요.
따라서 이번에는 파랑-초록 Kempe chain의 관점에서, 한쪽 chain의 색을 뒤바꿀 수 있습니다.
그러면 이번에도 사각형 위에 단 3개의 색만이 놓이게 되고, 위와 같은 원리로 모순이 발생합니다.
자. 이상에서 모든 케이스가 불가능함을 보였으므로, 귀류법에 의하여 maxinal planar graph인 minimal counterexample에는 차수 4인 점을 가지지 않습니다.////////
지금까지 우리가 해온걸 정리해봅시다.
먼저, 우리가 2부上에서 발견한 사실
“maximal planar graph 인 반례에는 반드시 차수 5 이하인 점이 존재한다.”
이 성립함과 동시에,
“maximal planar graph 인 반례 중 어떤 것(minimal counterexample) 에는 절대로 차수 1,2,3,4 인 점이 존재할 수 없다.”
도 성립함을 알았습니다.
이제, 다음을 보일 수 있다면..
“maximal planar 이면서 minimal counterexample인 어떤 그래프는 차수 1.2.3.4점은 커녕 차수 5인 것도 없다.”
그렇다면, 이건 우리가 2부上에서 발견한 것과 모순이죠. 그러면 증명은 끝납니다. 이것이 Kempe가 보이려고 했던 것이고.. 실제로 그는 보였습니다.
(라고 그는 생각했습니다.)
얼마 지나 그의 증명에서 결함이 발견되었죠. 그는 차수5인 점을 제거하는데 실패했던 것입니다.
2. 이제 어떡하죠
우리가 아는 사실을 좀 다른 식으로 표현해 봅시다. 앞으로 반례라고 말하면, 편의상 maximal planar 이면서 minimal 인 것을 지칭하는 것으로 합시다.
“반례에는 반드시 있어야 하는 점이 있다. (차수 1,2,3,4 또는 5인 점)”
“반례에는 반드시 없어야 하는 점도 있다. (차수 1,2,3그리고 4인 점)”
혹은 이렇게 표현해 봅시다.
“반례를 어떻게 만들어도 피할 수 없는 형태가 있다. 어떤 반례에도 아래의 형태 중 하나는 있어야 한다..”
우리가 앞에서 보았듯이 차수 3인 점의 주변 모양은 하나로 결정됩니다. 그래서 “점”에 대해 말하지 않고 이렇게 더 큰 “형태”에 대해서 말해도 돼요.
“반례에는 절대로 존재할 수 없는 형태도 있다. 어떤 반례에도 아래의 형태가 있다면, (우리가 앞에서 한 과정과 비슷한 방법으로) 4가지색만으로 그 그래프를 칠할 수 있게 된다. 아래와 같은 리스트를 가지면 그런 일이 일어난다..”
Appel과 Haken의 4색문제 풀이는 위의 명제에서 그림 부분만 바꾼 것과 다를바가 없습니다. 그들의 4색문제 첫 증명은 이런 식입니다.
4색문제가 거짓이라고 가정하자. 그러면 반례가 존재한다.
반례를 어떻게 만들어도 피할 수 없는 형태가 있다.그것은 아래와 같다.
.
.
.....
.
.
...
(이렇게 1936개)
반례에는 절대로 존재할 수 없는 형태도 있다. 그건 위에 그려진 것과 같다.
이건 모순이다. 따라서 4색 정리는 참이다.Q.E.D.
자. .. 이제 여러분은 이해하실 수 있습니다. 문제를 유한한 케이스로 나누어 컴퓨터에 집어넣었다는 것이 무엇인지를 말이죠. 그리고 그와 동시에 더 많은 질문이 생기실 겁니다.
그 질문들에 대한 대답은 다음 시간에.
참고 : 1.a끝부분에서 차수 1,2인 점을 제외하는데 사실 이 점들은 어려운 과정 없이 지도에서 만들어지는 그래프의 특징에 의해 즉시 케이스에서 제외됩니다. 서술의 복잡함을 피하기 위해서 그냥 차수 3인 경우와 같은 방법으로 풀었습니다.
subcase 3-2에서 암묵적으로 사용된 정리가 있는데, Jordan curve theorem입니다. Jordan curve theorem의 내용은 말하기에 어이가 없는데.. “평면에서 고리의 안과 밖은 분리되어 있다.” 거든요. 직관적으로 당연하지만 증명하기는 끔찍합니다. 우린 그냥 사용합시다.
