Theorem (König’s lemma).
Let be a rooted directed tree. If each vertex has finite degree but there are arbitrarily long rooted paths in , then contains an infinite path.
For each , let be a rooted path in of length , and let be the child of the root appearing in . By assumption, the set is finite. Since the set is infinite, the pigeonhole principle implies that there is a child of the root such that for infinitely many .
Now let us look at the subtree of rooted at . Each vertex has finite degree, and since there are paths of arbitrarily long length in passing through , there are arbitrarily long paths in rooted at . Hence if satisfies the hypothesis of the lemma, the root has a child such that also satisfies the hypothesis of the lemma. Hence we may inductively build up a path in of infinite length, at each stage selecting a child so that the subtree rooted at that vertex still has arbitrarily long paths. ∎
- 1 Kleene, Stephen., Mathematical Logic, New York: Wiley, 1967.