5색 정리

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

목차

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

1. 진술 _{✎ ⊖}

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

2. 증명 _{✎ ⊖}

2.1. 정의 _{✎ ⊖}

그래프 G에서 각 v∈V에 대해 색의 집합 C(v) (|C(v)|=k)가 어떻게 주어져도 이웃한 꼭짓점의 색이 다르도록 각 v가 C(v)의 한 색으로 색칠 가능한 k의 최솟값을 χ_l(G)라 한다. 그리고 C(v)들이 모두 같을 때 이웃한 꼭짓점의 색이 다르도록 색칠 가능한 k의 최솟값을 χ(G)라 한다.

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

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

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

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

유사삼각그래프 G=(V,E)와 그 외부 영역의 경계 B를 생각하자. V의 각 원소 v에게 준 색집합 C(v)에 아래 조건을 부여하자.

1. B의 두 이웃한 꼭짓점 x,y는 서로 다른 색 α,β로 각각 색칠되어있다.
2. ∀ v∈B∖\\{x,y\\}, |C(v)|≥3이다.
3. ∀ v∈V∖B, |C(v)|≥5이다.

그러면 G는 색칠 가능하다.

2.2.1. 증명 _{✎ ⊖}

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

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

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

2. 위와 같은 u,v가 존재하지 않을 때
v_0를 B 위에서 x를 기준으로 y 반대쪽에 있는 점이라고 하고, v_0와 이웃한 점들을 x,v_1,v_2,⋯,v_n,_z (v_i∈V∖B, z∈B)라 하자. |C(v)|≥3에서 |C(v)∖\\{α\\}|≥2이므로 γ,δ∈C(v)∖\\{α\\}, γ≠δ인 γ,δ가 존재한다. 이제 G에서 v_0과 연결된 변들을 제거하고, C(v_i)를 C(v_i)∖γ,δ로 바꾸어 새로운 그래프를 만들자. 귀납가설에 의해 이 그래프는 색칠 가능하다. 다시 v_0를 추가하고, γ,δ 중 z의 색이 아닌 것으로 v_0를 색칠하면 G의 색칠이 완료된다.

따라서 증명이 끝났다.

위 정리에 의해 χ_l(G)≤5이고, χ(G)≤χ_l(G)에서 χ(G)≤5를 얻는다.

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

1. 진술 ✎ ⊖

2. 증명 ✎ ⊖

2.1. 정의 ✎ ⊖

2.2. 더 강력한 정리 ✎ ⊖

2.2.1. 증명 ✎ ⊖

1. 진술 _{✎ ⊖}

2. 증명 _{✎ ⊖}

2.1. 정의 _{✎ ⊖}

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

2.2.1. 증명 _{✎ ⊖}