The Dinitz Problem (편집) (5)

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

[math(\cup_{v \in V}C(v))]의 한 원소 [math(c)]를 잡고, [math(V_c:={v \in V \mid c \in C(v)})]라 하자.

[math(V_c)]에 의해 induce된 부분그래프는 가정에 의해 kernel [math(K)]가 존재한다. 이제 [math(V \setminus K)]에 의해 induce된 부분그래프 [math(G’)]를 생각하고, 각 [math(v \in V \setminus K)]에 대해 [math(C’(v)=C(v) \setminus {c})]를 주자.

[math(G’)]의 꼭짓점의 개수는 [math(|V|-|K| < |V|)]이며, 각 [math(u \in V \setminus K)]에 대해

[math(c \in C(u) : |C’(u)| = |C(u)|-1 \geq d_{\text{before}}^{+}(u) \geq d_{\text{after}}^{+}(u) +1)]

[math(c \notin C(u) : |C’(u)|=|C(u)| \geq d_{\text{before}}^{+}(u)+1 \geq d_{\text{after}}^{+}(u)+1)]

이고[math(K)]가 [math(V_c)]에 의해 induced된 부분그래프의 kernel이므로 [math(c \in C(u))]인 경우 [math(u \in V_c)]에서 [math(v \in K)]가 존재하여 [math((u \to v) \in E)]인데 [math(G’)]에서는 이 [math(u \to v)]들이 제거되므로 [math(d^{+}(u))]가 감소하여 [math(d_{\text{before}}^{+}(u) \geq d_{\text{after}}^{+}(u) +1)]이 된다. [math(c \notin C(u))]일 경우 [math(d^{+}(u))]는 감소하거나 일정하므로 [math(d_{\text{before}}^{+}(u)+1 \geq d_{\text{after}}^{+}(u)+1)]이다.),

[math(\vec{G})]의 임의의 induce된 부분그래프의 kernel이 존재함에서 [math(\vec{G’})]의 임의의 induce된 부분그래프의 kernel 또한 존재하므로 [math(G’)]은 조건을 모두 만족한다. 따라서 귀납가설에 의해 [math(G’)]의 색칠이 존재한다. 이제 이 색칠에 [math(c)]로 색칠된 [math(K)]의 원소들과 제거했던 변들을 추가하면 [math(G)]의 색칠이 완성된다. 따라서 증명이 끝났다.

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

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

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

[math(\cup_{v \in V}C(v))]의 한 원소 [math(c)]를 잡고, [math(V_c:={v \in V \mid c \in C(v)})]라 하자.

[math(G’)]의 꼭짓점의 개수는 [math(|V|-|K| < |V|)]이며, 각 [math(u \in V \setminus K)]에 대해

[math(c \in C(u) : |C’(u)| = |C(u)|-1 \geq d_{\text{before}}^{+}(u) \geq d_{\text{after}}^{+}(u) +1)]

[math(c \notin C(u) : |C’(u)|=|C(u)| \geq d_{\text{before}}^{+}(u)+1 \geq d_{\text{after}}^{+}(u)+1)]

비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.

편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이 CC BY 4.0에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.