# 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\geq 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\geq 1\}$ is finite. Since the set $\{P_{n}\mid n\geq 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. ∎

## References

• 1 Kleene, Stephen., Mathematical Logic, New York: Wiley, 1967.
Title König’s lemma KonigsLemma 2013-03-22 15:38:26 2013-03-22 15:38:26 mps (409) mps (409) 6 mps (409) Theorem msc 05C05 Koenig’s lemma