5색 정리 (편집) - 시드위키

[[분류:가져온 문서/오메가]]
5색 정리는 4색 정리의 4가 5로 바뀐 것이다.

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

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

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

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

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

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

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

그러면 [math(G)]는 색칠 가능하다.

==== 증명 ====
[math(|V|)]에 대한 귀납법을 사용한다.

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

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

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

따라서 증명이 끝났다.

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

== 영상 ==
[youtube(kxg8u1UU6LI)]

[Include(틀:가져옴,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]], L=[[https://archive.ph/2mAEM|링크]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)