|
König's Tree Lemma
Lemma
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_{n+1}$ is a child of $t_n$;
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:
- 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
Source of Name
This entry was named for Dénes Kőnig.
Sources
| 
