쾨니그 보조정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''쾨니그 보조정리'''(Kőnig補助定理, {{llang|en|Kőnig’s lemma}})는 어떤 그래프가 무한할 수 있는 방법들을 나열하는 정리다.

== 정의 ==
'''쾨니그 보조정리'''에 따르면, 임의의 [[그래프]] <math>G</math>에 대하여, 다음 네 명제 가운데 적어도 하나가 성립한다.
* <math>G</math>는 유한 개의 [[꼭짓점]]을 갖는다.
* <math>G</math>는 무한 개의 [[연결 그래프|연결 성분]]을 갖는다.
* <math>G</math>는 차수가 무한한 꼭짓점을 갖는다.
* <math>G</math>는 무한 [[경로 (그래프 이론)|경로]]를 갖는다.

이 정리는 [[체르멜로-프렝켈 집합론]]에서는 증명될 수 없으나, [[의존적 선택 공리]]를 추가한 [[체르멜로-프렝켈 집합론]]에서는 증명된다. 다만, 만약 <math>G</math>가 오직 [[가산 무한]] 개의 꼭짓점을 갖는 경우에는 [[체르멜로-프렝켈 집합론]]에서 증명된다.

== 증명 ==
[[수학적 귀납법]]을 사용하여, 다음 보조정리를 증명하면 족하다.

<math>G</math>가 다음 성질들을 만족시키는 [[그래프]]라고 하자.
* <math>G</math>는 무한한 수의 꼭짓점을 갖는다.
* <math>G</math>는 유한 개의 연결 성분을 갖는다.
* <math>G</math>의 모든 꼭짓점의 차수는 유한하다.
* <math>G</math>는 길이가 <math>n\in\mathbb N</math>인 [[경로 (그래프 이론)|경로]] <math>v_0v_1\dots v_n</math>을 갖는다.
* <math>v_n</math>은 <math>G\setminus\{v_0,v_1,\dots,v_{n-1}\}</math>의 연결 성분 가운데 무한한 크기의 성분 <math>G_n</math>에 포함된다.
그렇다면 다음이 성립한다.
* <math>G</math>는 길이가 <math>n+1</math>인 경로 <math>v_0v_1\dots v_nv_{n+1}</math>을 가지며, 또한 <math>v_{n+1}</math>은 <math>G\setminus\{v_0,v_1\dots,v_n\}</math>의 연결 성분 가운데 무한한 크기의 성분 <math>G_{n+1}</math>에 포함된다.

이 보조정리는 다음과 같이 보일 수 있다. <math>G_n\setminus\{v_n\}</math>은 <math>\deg v_n</math>개 이하의 수의 연결 성분을 갖는 무한 그래프이다. 따라서, <math>G_n\setminus\{v_n\}</math>의 연결 성분 가운데 적어도 하나는 무한 그래프이다. 이 성분을 <math>G_{n+1}</math>이라고 하고, <math>v_{n+1}</math>이 <math>G_{n+1}</math>에 속한, <math>v_n</math>에 연결된 임의의 꼭짓점이라고 하자. 그렇다면 <math>v_0v_1\cdots v_nv_{n+1}</math> 및 <math>G_{n+1}</math>은 보조정리의 조건을 충족시킨다.

보조정리가 증명되었으며, <math>n=0</math>일 경우는 자명하므로 (<math>v_0</math>을 <math>G</math>의 성분 가운데 무한한 크기의 것에서 고른다), 쾨니그 보조정리가 증명된다.

== 역사 ==
[[쾨니그 데네시]]가 1927년에 증명하였다.<ref>{{저널 인용 | last = König | first = D. | authorlink = 쾨니그 데네시 | 권 = 3 | 호 = 2–3 | journal = Acta Scientiarum Mathematicarum Universitatis Szegediensis | 언어 = de | pages = 121–130 | title = Über eine Schlussweise aus dem Endlichen ins Unendliche | url = http://acta.fyx.hu/acta/showCustomerArticle.action?id=5131&dataObjectType=article | 날짜 = 1927 | issn = 0001-6969 | 확인날짜 = 2015-01-01 | 보존url = https://web.archive.org/web/20150101195126/http://acta.fyx.hu/acta/showCustomerArticle.action?id=5131&dataObjectType=article# | 보존날짜 = 2015-01-01 | url-status = dead }}</ref><ref>{{저널 인용
 | last = Franchella | first = Miriam
 | 권 = 51 | 호 = 1
 | journal = Archive for History of Exact Sciences
 | pages = 3-27
 | title = On the origins of Dénes König’s infinity lemma
 | doi = 10.1007/BF00376449
 | 날짜 = 1997-07-22 | issn=0003-9519 | 언어=en}}</ref>

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=KoenigsLemma|title=König's lemma|저자=Alex Sakharov }}

[[분류:보조정리]]
[[분류:계산 가능성 이론]]
[[분류:기초관계]]
[[분류:그래프 이론]]
[[분류:구성주의 (수학)]]
[[분류:선택 공리]]