쾨니그 보조정리

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

정의

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

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

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

증명

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

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

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

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

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

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

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

역사

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