When dealing with finite graphs, it's normal to define (rooted) trees in a graph-theoretic way: a tree is a directed graph with a designated root in which each vertex has a unique walk to the root. The ancestor-descendant relation can be derived from this: an ancestor of \( x \) is a vertex that can be reached by a walk from \( x. \) However, it's also possible to turn this around, and define trees in terms of their ancestor-descendant relations, with the parent-child relation derived from that. In the turned-around definition, a tree is a partial order with a designated root element that is a predecessor of every element, such that the predecessors of each element are totally ordered. The parent of an element would then be the maximum of its predecessors. So graph-theoretic finite trees and order-theoretic finite trees are really the same things as each other, in a different disguise. But that's no longer true when we go from finite to infinite: we can define trees in either of these two ways, but we get different things.

An infinite graph-theoretic tree can be defined in the same way as a finite one: a graph with a designated root in which each vertex has a unique walk to the root. But the usual order-theoretic definition of a tree takes a little more care: it is a partial order with a designated root element that is a predecessor of every element, as before, but where the predecessors of each element are required to be well-ordered, not just totally ordered. The ancestor-descendant relation in an infinite graph-theoretic tree gives a valid order-theoretic tree, but one in which the predecessors of each element form a finite total order. Allowing the predecessors to be, instead, any well-ordering gives the order-theoretic trees greater generality over the graph-theoretic ones.

This distinction comes up in trying to generalize the notion of tree-depth to infinite graphs. For a finite graph \( G, \) the tree-depth is the minimum height of a rooted tree \( T \) on the same vertex set such that every edge in \( G \) connects an ancestor-descendant pair in \( T. \) That is, \( T \) should be a depth-first search tree for a supergraph of \( G. \) One can try using this definition directly for infinite graphs, with a graph-theoretic infinite tree, but then not all infinite graphs would have a defined tree-depth (for instance, what is the depth of an uncountable clique?). Another quirk of this kind of tree is that, in infinite graphs, depth-first search trees are not the same as spanning trees for which all other edges connect an ancestor-descendant pair. For instance, an uncountable star cannot be explored by depth-first search but clearly is itself such a spanning tree.

Instead, I think the right notion of tree-depth, for infinite graphs, uses the order-theoretic notion of a tree. For any graph \( G, \) the axiom of choice implies the existence of some order-theoretic trees \( T \) such that every edge in \( G \) connects a pair of related elements of \( T. \) One way of finding such a tree is to choose \( T \) to be any well-ordering of \( G, \) a tree with only one branch. (A branch of a tree is a maximal totally ordered subset of it.) We can define the tree-depth of \( G \) to be the minimum height of a tree \( T \) for which each edge of \( G \) connects a pair of related elements in \( T. \) Here, the height of an element of a tree is the order-type of its strict predecessors and the height of the tree itself is the least ordinal greater than the heights of all its elements. That is, according to this definition, the tree-depth of \( G \) should be an ordinal number. The fact that the ordinals are themselves well-ordered allows the “minimum height” part of the definition of tree-depth above to be well-defined: any set of ordinals, such as the set of heights of valid trees for a given graph \( G, \) has a unique smallest element.

Every graph with countably many vertices either has bounded tree-depth (a finite number, equivalent to the definition with graph-theoretic trees) or tree-depth \( \omega \) (the first infinite ordinal number), because we can just use as our tree the set of non-negative integers with their usual ordering (again, a tree with a single branch). However, there are graphs whose tree-depth is a bigger countable ordinal than this. For example, let \( G=(U,V,E) \) be a complete bipartite graph where one side of the bipartition \( U \) is countable and the other side \( V \) is uncountable. We can form a tree \( T \) on the vertices of \( G \) by choosing any one-to-one correspondence of \( U \) with the non-negative integers, and by making each vertex in \( V \) have all the vertices in \( U \) as its predecessors. This tree has height \( \omega+1, \) so \( G \) has tree-depth at most \( \omega+1. \) But there is no shorter tree for \( G, \) because in a shorter tree every vertex would have only finitely many predecessors. If each vertex in \( U \) has finitely many predecessors, then there are infinitely many vertices in \( V \) that are not predecessors of any vertex in \( U \). Each of these non-predecessor vertices must itself have infinitely many predecessors in a valid tree for \( G, \) causing the tree to have height at least \( \omega+1. \) So the tree-depth of \( G \) is exactly \( \omega+1. \)

More generally, a transfinite induction shows that every ordinal \( \alpha \) is the tree-depth of at least one graph \( G_{\alpha}. \) For, if \( \alpha \) is a limit ordinal, we can construct \( G_{\alpha} \) as a limit of the graphs for all smaller ordinals (for instance, by choosing a minimum-height tree for each of these smaller graphs and identifying these trees at their roots). And if \( \alpha \) is not a limit ordinal, then it equals \( \beta+1 \) for some other ordinal \( \beta. \) Choose a cardinal \( \kappa \) bigger than the cardinality of \( \alpha, \) a graph \( G_{\beta} \) with tree-depth \( \beta, \) and a tree \( T_{\beta} \) realizing the tree-depth of \( G_{\beta}. \) Then we can construct \( G_{\alpha} \) by adding \( \kappa \) new vertices for each branch of \( G_{\beta}, \) where each newly added vertex is adjacent to everything in its branch. This graph \( G_{\alpha} \) has an associated tree \( T_{\alpha} \) of height \( \alpha, \) in which the predecessor set of each newly added vertex is the branch of \( T_{\beta} \) that it was added to. An argument like the one for the infinite complete bipartite graph shows that in any tree for \( G_{\alpha}, \) at least one of the new vertices has to be completely above its branch, forcing the tree to have height at least \( \alpha. \)

So graph-theoretic trees and finite natural numbers are not good enough to define a notion of tree-depth for all infinite graphs, but order-theoretic trees and ordinal numbers suffice. And if you define tree-depth in this way, every ordinal number occurs as the tree-depth of at least one graph.