I have a tree with the following properties:
- There is a countable number of vertices.
- Vertices can have a countable number of "sons".
- At each depth, there exists at least a vertex who has a "descendant" at each following depth (those descendants, a priori, are not related in any other way).
Said differently and in formal terms, if we consider that the tree represents the partial order $\leq$, where the root is the minimum – each son being greater than its father and unrelated vertices being uncomparable -, and if we denote by $V_n$ the set of vertices of depth $n$, then:
$\forall n, \exists v \in V_n, \forall m>n, \exists u_m \in V_m, v \leq u_m$
The question is: does the tree possess an infinite branch ?
Best Answer
Edit:
We can define a counterexample. For $n$ a natural number, define $T_n$ to be the tree starting with one vertex $v_n$ in degree $n$, and adding for every $m>n$ a linear branch of length $m-n$. Now let $T$ be the union of all these trees. All these trees are countable, and hence their union is countable. However, there is clearly not an infinite path since every branch is inherently finite.
Wrong answer:
If connections between vertices are only allowed between adjacent degrees, then yes, the tree has an infinite branch, and its proof is related to the one of König's Lemma. We start at degree $n=0$, in particular at the vertex $x_0$ such that there are descendants of $x_0$ for every $m>0$. We now want to decide to which vertex $x_1$ we go. Because $x_0$ has descendants for every $m>0$ there must in particular be some vertex $x_1$ which also has descendants for every $m>0$. We pick this one as the next vertex in our branch. We continue like this and find an infinite path.
If we are also allowed to have paths between vertices which differ more than one in their degree, then we can find a counterexample to the statement. We define $T_n$ to be a tree which has its origin in degree $n$, and has one descendant in every degree $m>n$, which are mutually incomparible. So, for $T_0$ this tree has vertices $v_0,\ldots, v_n,\ldots$ for every $n$, with just the edges $(v_0,v_i)$. Now, we take the union $\bigcup T_n$ of all these trees and obtain a counterexample.
Hope this helps!