(+)분류 : 가져온 문서/오메가
5색 정리는 4색 정리의 4가 5로 바뀐 것이다.
1. 진술 ✎ ⊖
임의의 평면 그래프는 서로 다른 5개의 색을 이용해 이웃한 두 꼭짓점의 색이 다르도록 색칠 가능하다.
2. 증명 ✎ ⊖
2.1. 정의 ✎ ⊖
그래프 에서 각 에 대해 색의 집합 가 어떻게 주어져도 이웃한 꼭짓점의 색이 다르도록 각 가 의 한 색으로 색칠 가능한 의 최솟값을 라 한다. 그리고 들이 모두 같을 때 이웃한 꼭짓점의 색이 다르도록 색칠 가능한 의 최솟값을 라 한다.
연결되었으며 경계가 있는 모든 면이 세 변을 갖는 평면그래프를 유사삼각하다고 하자.
그리고 ‘색칠’을 ‘이웃한 두 꼭짓점의 색이 다른 색칠’이라는 뜻으로 사용하겠다.
가 G의 부분그래프라면, 이다. 따라서 유사삼각그래프에 대해서만 증명하면 증명이 완성된다.
연결되었으며 경계가 있는 모든 면이 세 변을 갖는 평면그래프를 유사삼각하다고 하자.
그리고 ‘색칠’을 ‘이웃한 두 꼭짓점의 색이 다른 색칠’이라는 뜻으로 사용하겠다.
가 G의 부분그래프라면, 이다. 따라서 유사삼각그래프에 대해서만 증명하면 증명이 완성된다.
2.2. 더 강력한 정리 ✎ ⊖
유사삼각그래프 와 그 외부 영역의 경계 를 생각하자. 의 각 원소 에게 준 색집합 에 아래 조건을 부여하자.
1. 의 두 이웃한 꼭짓점 는 서로 다른 색 로 각각 색칠되어있다.
2. 이다.
3. 이다.
그러면 는 색칠 가능하다.
1. 의 두 이웃한 꼭짓점 는 서로 다른 색 로 각각 색칠되어있다.
2. 이다.
3. 이다.
그러면 는 색칠 가능하다.
2.2.1. 증명 ✎ ⊖
에 대한 귀납법을 사용한다.
인 경우는 자명하게 성립한다. 그 이상의 경우에 대해 증명하자.
1. 인 가 존재할 때
이 때 이거나 를 기준으로 가 같은 방향에 있게 된다. 전자의 경우 를 기준으로 나뉘어진 두 부분그래프가 색칠 가능하므로 또한 색칠 가능하다. 그리고 후자의 경우 우선 에 의해 나뉘어진 두 부분그래프 중 가 포함된 부분그래프를 색칠한 후 반대쪽 부분그래프를 색칠하면 (가 색칠된 상태이므로 가정의 1번 조건을 만족하여 색칠 가능하다) 의 색칠이 완료된다. 부분그래프의 색칠가능성은 귀납가설에 의해 보장된다.
2. 위와 같은 가 존재하지 않을 때
를 위에서 를 기준으로 반대쪽에 있는 점이라고 하고, 와 이웃한 점들을 라 하자. 에서 이므로 인 가 존재한다. 이제 에서 과 연결된 변들을 제거하고, 를 로 바꾸어 새로운 그래프를 만들자. 귀납가설에 의해 이 그래프는 색칠 가능하다. 다시 를 추가하고, 중 의 색이 아닌 것으로 를 색칠하면 의 색칠이 완료된다.
따라서 증명이 끝났다.
위 정리에 의해 이고, 에서 를 얻는다.
인 경우는 자명하게 성립한다. 그 이상의 경우에 대해 증명하자.
1. 인 가 존재할 때
이 때 이거나 를 기준으로 가 같은 방향에 있게 된다. 전자의 경우 를 기준으로 나뉘어진 두 부분그래프가 색칠 가능하므로 또한 색칠 가능하다. 그리고 후자의 경우 우선 에 의해 나뉘어진 두 부분그래프 중 가 포함된 부분그래프를 색칠한 후 반대쪽 부분그래프를 색칠하면 (가 색칠된 상태이므로 가정의 1번 조건을 만족하여 색칠 가능하다) 의 색칠이 완료된다. 부분그래프의 색칠가능성은 귀납가설에 의해 보장된다.
2. 위와 같은 가 존재하지 않을 때
를 위에서 를 기준으로 반대쪽에 있는 점이라고 하고, 와 이웃한 점들을 라 하자. 에서 이므로 인 가 존재한다. 이제 에서 과 연결된 변들을 제거하고, 를 로 바꾸어 새로운 그래프를 만들자. 귀납가설에 의해 이 그래프는 색칠 가능하다. 다시 를 추가하고, 중 의 색이 아닌 것으로 를 색칠하면 의 색칠이 완료된다.
따라서 증명이 끝났다.
위 정리에 의해 이고, 에서 를 얻는다.
