5색 정리

5색 정리는 4색 정리의 4가 5로 바뀐 것이다.

목차

1. 진술
2. 증명
2.1. 정의
2.2. 더 강력한 정리
2.2.1. 증명

1. 진술 _{✎ ⊖}

임의의 평면 그래프는 서로 다른 5개의 색을 이용해 이웃한 두 꼭짓점의 색이 다르도록 색칠 가능하다.

2. 증명 _{✎ ⊖}

2.1. 정의 _{✎ ⊖}

그래프 에서 각 에 대해 색의 집합 가 어떻게 주어져도 이웃한 꼭짓점의 색이 다르도록 각 가 의 한 색으로 색칠 가능한 의 최솟값을 라 한다. 그리고 들이 모두 같을 때 이웃한 꼭짓점의 색이 다르도록 색칠 가능한 의 최솟값을 라 한다.

연결되었으며 경계가 있는 모든 면이 세 변을 갖는 평면그래프를 유사삼각하다고 하자.

그리고 ‘색칠’을 ‘이웃한 두 꼭짓점의 색이 다른 색칠’이라는 뜻으로 사용하겠다.

가 G의 부분그래프라면, 이다. 따라서 유사삼각그래프에 대해서만 증명하면 증명이 완성된다.

2.2. 더 강력한 정리 _{✎ ⊖}

유사삼각그래프 와 그 외부 영역의 경계 를 생각하자. 의 각 원소 에게 준 색집합 에 아래 조건을 부여하자.

1. 의 두 이웃한 꼭짓점 는 서로 다른 색 로 각각 색칠되어있다.
2. 이다.
3. 이다.

그러면 는 색칠 가능하다.

2.2.1. 증명 _{✎ ⊖}

에 대한 귀납법을 사용한다.

인 경우는 자명하게 성립한다. 그 이상의 경우에 대해 증명하자.

1. 인 가 존재할 때
이 때 이거나 를 기준으로 가 같은 방향에 있게 된다. 전자의 경우 를 기준으로 나뉘어진 두 부분그래프가 색칠 가능하므로 또한 색칠 가능하다. 그리고 후자의 경우 우선 에 의해 나뉘어진 두 부분그래프 중 가 포함된 부분그래프를 색칠한 후 반대쪽 부분그래프를 색칠하면 (가 색칠된 상태이므로 가정의 1번 조건을 만족하여 색칠 가능하다) 의 색칠이 완료된다. 부분그래프의 색칠가능성은 귀납가설에 의해 보장된다.

2. 위와 같은 가 존재하지 않을 때
를 위에서 를 기준으로 반대쪽에 있는 점이라고 하고, 와 이웃한 점들을 라 하자. 에서 이므로 인 가 존재한다. 이제 에서 과 연결된 변들을 제거하고, 를 로 바꾸어 새로운 그래프를 만들자. 귀납가설에 의해 이 그래프는 색칠 가능하다. 다시 를 추가하고, 중 의 색이 아닌 것으로 를 색칠하면 의 색칠이 완료된다.

따라서 증명이 끝났다.

위 정리에 의해 이고, 에서 를 얻는다.

이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.
본 문서의 원본은 링크에서 확인할 수 있습니다.

분류 : 가져온 문서/오메가

1. 진술 ✎ ⊖

2. 증명 ✎ ⊖

2.1. 정의 ✎ ⊖

2.2. 더 강력한 정리 ✎ ⊖

2.2.1. 증명 ✎ ⊖

1. 진술 _{✎ ⊖}

2. 증명 _{✎ ⊖}

2.1. 정의 _{✎ ⊖}

2.2. 더 강력한 정리 _{✎ ⊖}

2.2.1. 증명 _{✎ ⊖}