2
$\begingroup$

I am reading a book of Michael Sipser "Introduction to the theory of computation", and there is a theorem, which he gives without a proof: "If every node of a tree has only finitely many children and every branch of the tree has finitely many nodes, the tree itself has only finitely many nodes."

Could you, please, help with a proof of this theorem.

1 Answers 1

8

This is more often stated in the form "if a tree $T$ is infinite and every node has only finitely many children then there exists an infinite path in $T$" (see König's Lemma). The infinite path may be constructed as follows: Let $x_0$ denote the root of $T$. Now $x_0$ has only finitely many children but $T$ is infinite so there must be at least one child of $x_0$ such that the subtree under it is infinite. We call this child $x_1$. Now the subtree with root $x_1$ has also the property that every node has only finitely many children so we may continue in the same way as before and choose a child $x_2$ of $x_1$ such that the subtree with root $x_2$ is infinite etc. This yields an infinite path $x_0,x_1,x_2,\ldots$

  • 0
    @ZhenLin, and Brian Scott: suppose each node has degree 2 or 3, and that the tree is "asymmetric", ie at leach level (distance from root) the degrees of the neighborhood of each node are onto {2,3} (might need some other assumptions here). How would such a tree relate to choice as opposed to a complete binary tree? (Bertrand Russell in "Philosophy of Mathematics" describes the sequence of identical socks versus distinct shoes as making the difference in choice assumption).2012-08-19