# About finiteness of trees

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.

-

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$

-
One wonders if we really need the axiom of choice here, though... –  Zhen Lin Aug 19 '12 at 12:55
@Zhen Lin: You need a bit of it for the general case of König’s lemma. –  Brian M. Scott Aug 19 '12 at 13:03
Indeed, hence my comment! Yet for some reason my mind thinks that the theorem, when phrased this way entirely finitistic terms, should admit a solution without AC. Maybe that's just bad intuition... –  Zhen Lin Aug 19 '12 at 13:10
@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). –  alancalvitti Aug 19 '12 at 17:46