König’s lemma

Theorem (König’s lemma).

Let $T$ be a rooted directed tree. If each vertex has finite degree but there are arbitrarily long rooted paths in $T$, then $T$ contains an infinite path.

Proof.

For each $n\ge 1$, let $P_n$ be a rooted path in $T$ of length $n$, and let $c_n$ be the child of the root appearing in $P_n$. By assumption, the set $\{c_n\mid n\ge 1\}$ is finite. Since the set $\{P_n\mid n\ge 1\}$ is infinite, the pigeonhole principle implies that there is a child $c$ of the root such that $c=c_n$ for infinitely many $n$.

Now let us look at the subtree $T_c$ of $T$ rooted at $c$. Each vertex has finite degree, and since there are paths $P_n$ of arbitrarily long length in $T$ passing through $c$, there are arbitrarily long paths in $T_c$ rooted at $c$. Hence if $T$ satisfies the hypothesis of the lemma, the root has a child $c$ such that $T_c$ also satisfies the hypothesis of the lemma. Hence we may inductively build up a path in $T$ of infinite length, at each stage selecting a child so that the subtree rooted at that vertex still has arbitrarily long paths. ∎

Title	König’s lemma
Canonical name	KonigsLemma
Date of creation	2013-03-22 15:38:26
Last modified on	2013-03-22 15:38:26
Owner	mps (409)
Last modified by	mps (409)
Numerical id	6
Author	mps (409)
Entry type	Theorem
Classification	msc 05C05
Synonym	Koenig’s lemma