📂그래프이론

5색 정리 증명

정리 ¹

모든 심플 평면 그래프는 $5$-채색가능하다.

설명

이 정리는 4색 문제와 구분하는 의미에서 5색 정리라는 이름이 붙었다. 역사적으로는 4색 정리를 증명하려고 했지만 증명에 번번히 실패했고, 대신 조금 완화된 팩트로써 증명되었다.

증명

전략: 수학적 귀납법을 사용한다. $n-1$ 개의 버텍스를 가진 심플 평면 그래프가 모두 $5$-채색가능하다고 가정했을 때, 버텍스가 하나 더 많아도 여전히 $5$-채색가능함을 보일 것이다.

---

$n-1$ 개의 버텍스를 가진 심플 평면 그래프가 모두 $5$-채색가능하다고 가정하자.

심플 평면 그래프의 성질 [2]: 모든 심플 평면 그래프 $G$ 는 $\deg v \le 5$ 인 버텍스 $v \in V(G)$ 를 가진다.

$G$ 가 $n$ 개의 버텍스를 가진 심플 평면 그래프면 그 성질에 따라 $\deg v \le 5$ 인 $v \in V(G)$ 가 존재한다. 이 $v$ 가 $5$-채색가능성에 문제를 일으키지 않는다면 $v$ 가 빠진 그래프 $G - v$ 는 $n-1$ 개의 버텍스를 가지므로 $5$-채색가능하고, $G$ 역시 $5$-채색가능이다.

만약 $\deg v < 5$ 면, $v$ 의 채색은 무엇이 되든 상관 없다.

만약 $\deg v = 5$ 면, $v$ 와 인접한 버텍스를 $v_{1} , \cdots , v_{5}$ 라 두고 $v$ 의 컬러를 $c$ 라 하자.

쿠라토프스키 정리: 그래프가 평면 그래프인 것과 그 그래프의 서브 그래프 중 $K_{5}$ 나 $K_{3,3}$ 과 호메오멀픽한 것이 없는 것은 동치다.

$G$ 는 평명 그래프이므로 $v_{1} , \cdots , v_{5}$ 는 서브 컴플리트 그래프 $K_{5}$ 를 이루어서는 안 된다. 따라서 이 중 적어도 두 버텍스는 인접하지 않아야한다. 일반성을 잃지 않고, 이 두 버텍스를 $v_{1} , v_{2}$ 라 하자. 이에 대해 $vv_{1}$ 과 $vv_{2}$ 를 수축시켜서 얻는 그래프는 $n-2$ 개의 버텍스를 가지므로 $5$-채색가능이다. 이제 수축했던 그래프의 $v_{1}$ 과 $v_{2}$ 를 원래대로 되돌려 놓으면서, $c$ 로 채색한다. 그러면 $v$ 는 $v_{3} , v_{4}, v_{5}$ 의 색이 모두 달라도 $c$ 를 포함해 최대 $4$ 가지 다른 색의 버텍스와 인접하므로, 남는 색 하나를 골라 채색함으로써 $5$-채색을 할 수 있다.

■