König's Tree Lemma

Theorem

Let $T$ be a rooted tree with an infinite number of nodes, each with a finite number of children.

Then $T$ has a branch of infinite length.

Proof

We will show that we can choose an infinite sequence of nodes $t_0, t_1, t_2, \ldots$ of $T$ such that:

• $t_0$ is the root node;

• $t_{n+1}$ is a child of $t_n$;

• Each $t_n$ has infinitely many descendants.

Then the sequence $t_0, t_1, t_2, \ldots$ is such a branch of infinite length.

Take the root node $t_0$.

By definition, it has a finite number of children.

Suppose that all of these childen had a finite number of descendants.

Then that would mean that $t_0$ had a finite number of descendants, and that would mean $T$ was finite.

So $t_0$ has at least one child with infinitely many descendants.

Thus, we may pick $t_1$ as any one of those children.

Now, suppose node $t_k$ has infinitely many descendants.

As $t_k$ has a finite number of children, by the same argument as above, $t_k$ has at least one child with infinitely many descendants.

Thus we may pick $t_{k+1}$ which has infinitely many descendants.

The assertion follows by induction.

$\blacksquare$

Note

This result does not hold if there exists at least one node which has an infinite number of children.

For example, let $T$ be the rooted tree defined as follows:

• $t_0$ is the root node.

• For all $n \in \N: n > 0$: $t_n$ is a leaf node which is a child of $t_0$.

Then there is an infinite number of nodes of $T$.

However, each branch of $T$ is of length equal to $1$.

Also see

This is a special case of the trickier to prove König's Lemma, which is a result that applies to all connected infinite graphs whose nodes are all finite in degree.

Also known as

This theorem is also referred to as König Tree Lemma, König's Tree Theorem and König Tree Theorem.

Source of Name

This entry was named for Dénes Kőnig.

Sources

• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.11$: Theorem $1.11.3$