쾨니그 보조정리
(쾨니그보조정리에서 넘어옴)
그래프 이론에서 쾨니그 보조정리(Kőnig補助定理, 영어: Kőnig’s lemma)는 어떤 그래프가 무한할 수 있는 방법들을 나열하는 정리다.
정의
편집쾨니그 보조정리에 따르면, 임의의 그래프 에 대하여, 다음 네 명제 가운데 적어도 하나가 성립한다.
이 정리는 체르멜로-프렝켈 집합론에서는 증명될 수 없으나, 의존적 선택 공리를 추가한 체르멜로-프렝켈 집합론에서는 증명된다. 다만, 만약 가 오직 가산 무한 개의 꼭짓점을 갖는 경우에는 체르멜로-프렝켈 집합론에서 증명된다.
증명
편집수학적 귀납법을 사용하여, 다음 보조정리를 증명하면 족하다.
가 다음 성질들을 만족시키는 그래프라고 하자.
- 는 무한한 수의 꼭짓점을 갖는다.
- 는 유한 개의 연결 성분을 갖는다.
- 의 모든 꼭짓점의 차수는 유한하다.
- 는 길이가 인 경로 을 갖는다.
- 은 의 연결 성분 가운데 무한한 크기의 성분 에 포함된다.
그렇다면 다음이 성립한다.
- 는 길이가 인 경로 을 가지며, 또한 은 의 연결 성분 가운데 무한한 크기의 성분 에 포함된다.
이 보조정리는 다음과 같이 보일 수 있다. 은 개 이하의 수의 연결 성분을 갖는 무한 그래프이다. 따라서, 의 연결 성분 가운데 적어도 하나는 무한 그래프이다. 이 성분을 이라고 하고, 이 에 속한, 에 연결된 임의의 꼭짓점이라고 하자. 그렇다면 및 은 보조정리의 조건을 충족시킨다.
보조정리가 증명되었으며, 일 경우는 자명하므로 ( 을 의 성분 가운데 무한한 크기의 것에서 고른다), 쾨니그 보조정리가 증명된다.
역사
편집참고 문헌
편집- ↑ König, D. (1927). “Über eine Schlussweise aus dem Endlichen ins Unendliche”. 《Acta Scientiarum Mathematicarum Universitatis Szegediensis》 (독일어) 3 (2–3): 121–130. ISSN 0001-6969. 2015년 1월 1일에 원본 문서에서 보존된 문서. 2015년 1월 1일에 확인함.
- ↑ Franchella, Miriam (1997년 7월 22일). “On the origins of Dénes König’s infinity lemma”. 《Archive for History of Exact Sciences》 (영어) 51 (1): 3–27. doi:10.1007/BF00376449. ISSN 0003-9519.
외부 링크
편집- Alex Sakharov. “König's lemma”. 《Wolfram MathWorld》 (영어). Wolfram Research.