지도를 4가지 색으로만 칠한다? 켐페 증명으로 밝혀진 놀라운 비밀!

네 가지 색깔 정리: 지도를 칠하는 마법

옛날 옛날 아주 먼 옛날, 수학자들이 이런 신기한 질문을 했어. "세상에 있는 모든 지도를 딱 네 가지 색깔만 가지고 칠할 수 있을까?" 여기서 지도는 나라나 주처럼 서로 연결된 지역들로 나뉜 걸 말해. 그리고 중요한 건, 서로 옆에 붙어 있는 나라(이웃한 지역)는 절대로 같은 색깔로 칠하면 안 된다는 거야.

놀랍게도, 수학자들은 "응, 네 가지 색깔이면 충분해!"라고 답했어. 이게 바로 네 가지 색깔 정리야.

지도를 그래프로 바꾸면?

이걸 좀 더 쉽게 이해하기 위해서, 지도를 '그래프'라는 걸로 바꿔서 생각해 볼 수 있어.

• 지역 하나하나를 그래프의 점(꼭짓점)이라고 생각하고,
• 두 지역이 서로 붙어 있으면 그 점들 사이에 선(변)을 긋는 거야.

이렇게 바꾸고 나면, 네 가지 색깔 정리는 이렇게 말하는 거랑 똑같아져.

"어떤 평면에 그려진 그래프든, 점들을 네 가지 색깔로 칠할 때, 서로 선으로 연결된 두 점은 절대로 같은 색깔이 아니게 칠할 수 있다!"

이런 그래프를 '4색 가능 그래프'라고 불러.

켐프의 증명 시도 (19세기 후반)

옛날에 켐프라는 수학자가 이 네 가지 색깔 정리가 왜 맞는지 증명하려고 했어. 마치 5가지 색깔 정리 증명처럼 말이야.

켐프는 이런 생각을 했어.

1. "어떤 그래프든, 연결된 선의 개수(차수)가 5개 이하인 점이 꼭 하나는 있어!"
2. "이걸 이용해서 '귀납법'으로 증명해 보자!"

귀납법이 뭐냐면,

• 점이 하나짜리 그래프는 당연히 색깔 하나로 칠할 수 있지? (정리가 성립!)
• 그럼 점이 n개인 그래프는 네 가지 색깔로 칠할 수 있다고 가정하자.
• 이제 점이 n+1개인 그래프도 네 가지 색깔로 칠할 수 있다는 걸 보여주면 돼!

어떻게 n+1개짜리 그래프를 칠할까?

자, 이제 점이 n+1개인 그래프가 있다고 생각해 봐. 여기서 특별한 점 V를 하나 골라. 이 점 V는 연결된 선이 5개 이하인 점이야.

만약 V가 4개의 점이랑 연결되어 있다면?

• 일단 V를 빼고 나머지 그래프를 네 가지 색깔로 칠할 수 있다고 가정하자. (귀납법 덕분!)
• V는 4개의 다른 점이랑 연결되어 있는데, 이 4개의 점이 만약 3가지 색깔만 썼다면? 그럼 V는 남은 1가지 색깔로 칠하면 끝!
• 근데 만약 이 4개의 점이 이미 네 가지 색깔을 다 써버렸다면? V를 무슨 색으로 칠해야 할까? 난감해지지.

이때 켐프는 "나머지 그래프의 색깔을 좀 바꿔서 V를 칠할 색깔을 만들어내자!"라고 생각했어.

색깔 바꾸는 마법 (체인 교환)

예를 들어, V가 빨간색 점과 파란색 점이랑 연결되어 있다고 해보자.

• 만약 빨간색 점과 파란색 점 사이에 '빨강-파랑-빨강-파랑...'으로 이어지는 길이 없다면?

  • 이럴 땐, 빨간색이랑 파란색을 쓴 길에서 색깔을 바꿔치기 할 수 있어! 빨간색을 파란색으로, 파란색을 빨간색으로 바꾸는 거지.
  • 이렇게 하면 V 옆에 빨간색 점이 없어지니까, V를 빨간색으로 칠할 수 있게 돼!

• 만약 빨간색 점과 파란색 점 사이에 '빨강-파랑-빨강-파랑...'으로 이어지는 길이 있다면?

  • 이때는 그냥 색깔을 바꾸면 똑같은 문제가 다시 생겨. 빨간색이 파란색이 되고 파란색이 빨간색이 되어도, V는 여전히 빨간색이나 파란색 점이랑 붙어 있게 되거든.

이럴 땐 다른 색깔(예: 파랑-초록)을 이용해 봐.

• 만약 파란색 점과 초록색 점 사이에 '파랑-초록-파랑-초록...'으로 이어지는 길이 없다면?
  • 마찬가지로 파란색과 초록색을 쓴 길에서 색깔을 바꿔치기 할 수 있어.
  • 이렇게 하면 V 옆에 파란색 점이 없어지니까, V를 파란색으로 칠할 수 있게 돼!

V가 5개의 점과 연결되어 있다면?

만약 V가 5개의 점과 연결되어 있고, 이 5개의 점이 네 가지 색깔을 다 써버렸다면? (예: 빨강, 파랑, 초록, 주황, 그리고 다시 파랑)

이때도 켐프는 비슷한 방식으로 색깔을 바꿔치기해서 V를 칠할 색깔을 만들려고 했어.

• 빨강-초록 체인이 연결되어 있지 않다면? 빨강과 초록을 바꿔치기해서 V를 빨강으로 칠할 수 있게 만들자!
• 빨강-초록 체인이 연결되어 있다면? 이건 좀 더 복잡해.
  • 그럼 이번엔 빨강-주황 체인을 보자.
  • 만약 빨강-주황 체인이 연결되어 있지 않다면? 빨강과 주황을 바꿔치기해서 V를 빨강으로 칠할 수 있게 만들자!
  • 만약 빨강-초록 체인도 연결되어 있고, 빨강-주황 체인도 연결되어 있다면? 이게 켐프가 가장 복잡하다고 생각했던 부분이야.

켐프는 이때 이런 생각을 했어.

"빨강-초록 체인이랑 빨강-주황 체인이 서로 얽혀 있으면, 마치 벽처럼 작용해서 다른 색깔(예: 파랑)들이 서로 연결되지 못하게 막아줘."

그래서 파랑-주황 체인이나 파랑-초록 체인에서 색깔을 바꿔치기하면, V를 파란색으로 칠할 수 있게 된다고 주장했지.

켐프의 증명, 사실은 틀렸어!

켐프는 1879년에 이 증명을 발표했고, 사람들은 이걸 믿었어. 그런데 10년쯤 뒤에 헤이워드라는 수학자가 켐프의 증명에 치명적인 오류를 발견했어!

헤이워드는 켐프가 생각하지 못한 특별한 그래프를 예로 들었어. V가 5개의 점과 연결되어 있고, 그 점들이 빨강, 파랑, 초록, 주황, 그리고 다시 빨강으로 연결된 경우였지.

이때 헤이워드는 켐프의 방법대로 색깔을 바꿔치기하려고 했더니, 결국 이웃한 두 점이 같은 색깔이 되어버리는 문제가 발생한다는 걸 보여줬어.

이건 정말 충격적인 발견이었지. 네 가지 색깔 정리 증명이 틀렸을 뿐만 아니라, 다른 수학자들이 제시한 증명들도 하나씩 오류가 발견되기 시작했어.

슈퍼컴퓨터의 등장과 진짜 증명

20세기에 들어서면서 수학자들은 이 문제를 해결하려고 계속 노력했지만, 점점 더 복잡한 경우의 수가 나타나서 증명이 어려워졌어.

결국, 1960년대와 70년대가 되어서야 슈퍼컴퓨터의 도움을 받아서 모든 경우의 수를 분석하고 나서야 비로소 네 가지 색깔 정리가 완벽하게 증명될 수 있었단다!