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 infiniteMathworldPlanetmath path.


For each n1, let Pn be a rooted path in T of length n, and let cn be the child of the root appearing in Pn. By assumptionPlanetmathPlanetmath, the set {cnn1} is finite. Since the set {Pnn1} is infinite, the pigeonhole principleMathworldPlanetmath implies that there is a child c of the root such that c=cn for infinitely many n.

Now let us look at the subtree Tc of T rooted at c. Each vertex has finite degree, and since there are paths Pn of arbitrarily long length in T passing through c, there are arbitrarily long paths in Tc rooted at c. Hence if T satisfies the hypothesis of the lemma, the root has a child c such that Tc 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. ∎


  • 1 Kleene, Stephen., Mathematical Logic, New York: Wiley, 1967.
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