쾨니그 보조정리

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

정의

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

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

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

증명

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

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

• $G$는 무한한 수의 꼭짓점을 갖는다.
• $G$는 유한 개의 연결 성분을 갖는다.
• $G$의 모든 꼭짓점의 차수는 유한하다.
• $G$는 길이가 $n\in \mathbb {N}$인 경로 $v_{0}v_{1}\dots v_{n}$을 갖는다.
• $v_{n}$은 $G\setminus \{v_{0},v_{1},\dots ,v_{n-1}\}$의 연결 성분 가운데 무한한 크기의 성분 $G_{n}$에 포함된다.

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

• $G$는 길이가 $n+1$인 경로 $v_{0}v_{1}\dots v_{n}v_{n+1}$을 가지며, 또한 $v_{n+1}$은 $G\setminus \{v_{0},v_{1}\dots ,v_{n}\}$의 연결 성분 가운데 무한한 크기의 성분 $G_{n+1}$에 포함된다.

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

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

역사

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

외부 링크

• Alex Sakharov. “König's lemma”. 《Wolfram MathWorld》 (영어). Wolfram Research.