【현대수학】 4색 정리

4색 정리(four color theorem)

 

추천글 : 【현대수학】 그래프 이론 

---

1. 정리 [본문]

2. 증명 [본문]

---

 

1. 정리 [목차]

모든 평면 지도는 4가지 색만으로 인접한 영역이 서로 다른 색이 되게 칠할 수 있다

 

 

2. 증명 [목차]

⑴ 1^st. 지도를 그래프로 변환

① 각 지역을 점으로 보고, 서로 국경을 맞대면 선으로 연결

② 주어진 문제는 모든 평면 그래프가 꼭짓점 4색칠이 가능한가로 바뀜 

 

 

⑵ 2^nd. 주어진 평면 그래프를 삼각분할 평면 그래프처럼 만듦

① 예시

 

# Before
A────B
│    │
│    │
D────C

# After
      A
     /|\
    / | \
   B--D--C
    \   /
     \ /
      C와 B는 바깥쪽 면을 따라 연결

 

② 모든 삼각분할 평면 그래프가 4색칠 가능하면 (더 어려운 문제), 모든 평면 그래프도 4색칠 가능함 (더 쉬운 문제)

⑶ 3^rd. 증명에 충분한 일부 불가피 집합을 탐색

① 불가피 집합(unavoidable set) : 어떤 평면 그래프가 주어져도, 그 그래프 안에 반드시 적어도 하나는 포함될 수밖에 없는 구조들의 모음

○ Appel–Haken의 1976년 증명에서는 약 1,834개의 reducible configuration을 컴퓨터로 확인 (ref)

○ 이후 일부 정리를 통해 1,482개로 줄어듦 (ref)

○ Robertson, Sanders, Seymour, Thomas가 1997년에 633개로 줄임 (ref) → 이후 설명은 633개로 통일 

② 예 1. 가장 단순한 불가피 집합 

○ 모든 면의 둘레 길이 합 = 2E ≥ 3F ⇔ F ≤ 2E / 3

○ 2 = V - E + F ≤ V - E + 2E / 3 ⇔ E ≤ 3V - 6

○ 모든 꼭짓점 차수가 6 이상이라고 가정하면, 전체 차수 합 = 2E ≥ 6V ≥ 2E + 12 (모순)

○ 평면 그래프에는 반드시 차수 5 이하인 꼭짓점이 적어도 하나 존재

○ 불가피 집합 = {차수 1 꼭짓점, 차수 2 꼭짓점, 차수 3 꼭짓점, 차수 4 꼭짓점, 차수 5 꼭짓점}

③ 예 2. 방전법 

○ 전하 = 6 - 차수로 정의하면, 전체 전하 합 = ∑(6 - 차수) = 6V - 2E = 6V - 2(3V - 6) = 12

○ 오일러 공식에서 나온 총 전하 12를 유지하면서 정해진 규칙(일관성만 있다면 임의로 지정해도 됨)에 따라 전하를 옮김

○ 정해진 규칙에 대응하여 양전하가 남아 있는 국소 패턴들 633개를 발견 (컴퓨터를 이용)

○ 633개의 국소 패턴이 없는 그래프는 모든 전하가 0 이하가 됨

○ 전체 전하 합이 12인데 모두 0 이하일 수는 없음

○ 따라서 633개의 구조 중 하나는 반드시 존재함

 

 

⑷ 4^th. 귀류법 : 4색칠이 안 되는 평면 그래프가 있고, 그 중 꼭짓점 수가 가장 적은 최소 반례를 가정 

① 최소 반례에서 633개의 구조 중 하나를 빼든 안 빼든 4색 정리의 성립 여부가 바뀌지 않음 (reducible)  (컴퓨터를 이용)

② 경우 1. 최소 반례에서 633개의 구조를 모두 뺐을 때 남는 게 있으면 이는 앞의 방전법에 위배되어 모순

③ 경우 2. 최소 반례에서 633개의 구조를 모두 뺐을 때 남는 게 없으면 그 자체는 4색 정리가 성립함을 말하므로 반례라는 사실과 모순

⑸ 5^th. 그러므로 그러한 반례는 없으며, 이로 인해 4색 정리는 성립함

⑹ 요약 

 

 

입력: 2026.02.07 11:10