쾨니그 보조정리

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

 정의 
쾨니그 보조정리에 따르면, 임의의 그래프 에 대하여, 다음 네 명제 가운데 적어도 하나가 성립한다.
 는 유한 개의 꼭짓점을 갖는다.
 는 무한 개의 연결 성분을 갖는다.
 는 차수가 무한한 꼭짓점을 갖는다.
 는 무한 경로를 갖는다.

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

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

가 다음 성질들을 만족시키는 그래프라고 하자.
 는 무한한 수의 꼭짓점을 갖는다.
 는 유한 개의 연결 성분을 갖는다.
 의 모든 꼭짓점의 차수는 유한하다.
 는 길이가 인 경로 을 갖는다.
 은 의 연결 성분 가운데 무한한 크기의 성분 에 포함된다.
그렇다면 다음이 성립한다.
 는 길이가 인 경로 을 가지며, 또한 은 의 연결 성분 가운데 무한한 크기의 성분 에 포함된다.

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

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

 역사 
쾨니그 데네시가 1927년에 증명하였다.

 참고 문헌 

 외부 링크 


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