König’s lemma

Theorem (König’s lemma).

Let $T$ be a rooted directed tree. If each vertex has finitedegree 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, thepigeonhole principle implies that there is a child $c$ of the rootsuch that $c=c_n$ for infinitely many $n$.

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