쾨니그 보조정리

그래프 이론에서, 쾨니그 보조정리(Kőnig補助定理, 영어: Kőnig’s lemma)는 어떤 그래프가 무한할 수 있는 방법들을 나열하는 정리다.

정의편집

쾨니그 보조정리에 따르면, 임의의 그래프  에 대하여, 다음 네 명제 가운데 적어도 하나가 성립한다.

  •  는 유한 개의 꼭짓점을 갖는다.
  •  는 무한 개의 연결 성분을 갖는다.
  •  는 차수가 무한한 꼭짓점을 갖는다.
  •  는 무한 경로를 갖는다.

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

증명편집

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

 가 다음 성질들을 만족시키는 그래프라고 하자.

  •  는 무한한 수의 꼭짓점을 갖는다.
  •  는 유한 개의 연결 성분을 갖는다.
  •  의 모든 꼭짓점의 차수는 유한하다.
  •  는 길이가  경로  을 갖는다.
  •   의 연결 성분 가운데 무한한 크기의 성분  에 포함된다.

그렇다면 다음이 성립한다.

  •  는 길이가  인 경로  을 가지며, 또한   의 연결 성분 가운데 무한한 크기의 성분  에 포함된다.

이 보조정리는 다음과 같이 보일 수 있다.   개 이하의 수의 연결 성분을 갖는 무한 그래프이다. 따라서,  의 연결 성분 가운데 적어도 하나는 무한 그래프이다. 이 성분을  이라고 하고,   에 속한,  에 연결된 임의의 꼭짓점이라고 하자. 그렇다면   은 보조정리의 조건을 충족시킨다.

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

역사편집

쾨니그 데네시가 1927년에 증명하였다.[1][2]

참고 문헌편집

  1. 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일에 확인함. 
  2. 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. 

외부 링크편집