Note
There are uncountably many topological typesof locally finite trees
Lilian Matthiesen
Mathematisches Seminar, Universität Hamburg, Bundesstraße 55, 20146
Hamburg, Germany; lilian.matthiesen@gmail.com

Abstract
Consider two locally finite rooted trees as equivalent if each of them is a topological minor of the other, with an embedding preserving the tree-order. Answering aquestion of van der Holst, we prove that there are uncountably many equivalenceclasses.
Key words: graph, locally finite tree, embedding, wqo, bqo

Let the tree-order ≤ on the set of vertices of a rooted tree T be defined by
setting x ≤ y for vertices x, y iff x lies on the unique path in T from its root
to y. Let us call two locally finite rooted trees equivalent if each of them is
a topological minor of the other, with an embedding that respects the treeorder. Call the equivalence classes topological types of such trees. The purposeof this note is to answer a question raised by van der Holst [2], by provingthat there are uncountably many topological types of locally finite trees.
Our proof uses Nash-Williams’s theorem that the – finite or infinite – rootedtrees are well-quasi-ordered under this relation: See Nash-Williams [4], orKühn [3] for a short proof. An introduction to the well-quasi-ordering of trees
can be found in Diestel [1, Ch.12]. For all terms that remain undefined here
we refer to [1].
Theorem 1 There are uncountably many topological types of locally finitetrees.
In the remainder of this note we prove Theorem 1. By 4 we denote the topological minor relation between rooted trees that respects their tree-order. LetT be a class of rooted trees. A tree T is said to be universal with respect to(T , 4), if T ∈ T and X 4 T for every X ∈ T .
Preprint submitted to Elsevier Science

25 January 2006

Note that the number of topological types of locally finite trees is not finite,since for instance any two finite trees of different order are of different topological type. Suppose there are only countably many topological types of locallyfinite trees. Let G1 be a set of locally finite trees, exactly one of each isomorphism type. Our aim is to construct a bad sequence T1 , T2 , . . . of trees in G1 ,i.e., a sequence T1 , T2 , . . . such that Ti 64 Tj whenever i < j.
To start with, choose trees X11 , X21 , . . . from G1 , exactly two trees of eachtopological type. Consider the disjoint countable union X11 ∪ X21 ∪ . . . and let
R1 = w11 w21 . . . be an additional ray. The tree T1 with root w11 is now obtainedby adding an edge for each i connecting wi1 and the root of Xi1 . Note thatT1 ∈ G1 .
LetForb(T1 , . . . , Tn ) := {G ∈ G1 | G 6< T1 , . . . , Tn }.
Similarly to the construction of T1 define trees Tn , n > 1, recursively as follows.
Assuming that Gn := Forb(T1 , . . . , Tn−1 ) contains infinitely many topologicaltypes of trees, let X1n , X2n , . . . ∈ Gn be a choice of exactly two trees of each type
represented in Gn . Consider the disjoint countable union X1n ∪ X2n ∪ . . . and
let Rn = w1n w2n . . . be an additional ray. Obtain Tn with root w1n by adding anedge for each i connecting win and the root of Xin .
Observe that if Tk exists and Tk ∈ Gk , our construction yields the following:(i) Tk is universal among all trees in Gk , since for any X ∈ Gk there is somej such that X 4 Xjk 4 Tk ;k(ii) Tk contains two disjoint representatives Xm, Xnk of its own topologicaltype. Denote these as Tk1 and Tk2 , let t1k and t2k be their roots, and let vk
be the first vertex on Rk adjacent to t1k or t2k . By construction, vk < t1k , t2kin the tree-order of Tk , and vk separates Tk1 from Tk2 in Tk ; in particular,
t1k and t2k are incomparable under the tree-order.
Lemma 2 For all natural n, Gn contains infinitely many topological types oftrees (so Tn exists), and Tn ∈ Gn .

PROOF. The assertion holds for n = 1. Let n > 1 and assume that Tk exists
and Tk ∈ Gk for every k < n. Then (i) and (ii) apply to these trees Tk .
By definition of Gn , every tree T ∈ G1 \ Gn satisfies T < Tk for some k < n.
Choose k minimum. Then T ∈ Forb(T1 , . . . , Tk−1 ) = Gk , and hence T 4 Tkby (i), so T and Tk have the same topological type. Thus, every T ∈ G1 \ Gnbelongs to one of finitely many topological types, those of T1 , . . . , Tn−1 . Henceas G1 contains trees of infinitely many types, so does Gn .
2

It remains to show that Tn ∈ Gn . If not, then Tn < Tk for some k < n. By
the induction hypothesis, Tk satisfies (ii). Given any (tree-order preserving)embedding of Tk into Tn , consider the images of t1k and t2k in Tn . Since incomparable vertices (with respect to the tree-order) map to incomparable vertices
under such an embedding, (ii) implies that not both t1k and t2k map to vertices
on Rn . Therefore one of them, tik , maps into some Xjn . Then Tki too maps intoXjn , contradicting the fact that Tki has the same topological type as Tk but
Xjn ∈ Forb(T1 , . . . , Tk , . . . , Tn−1 ). 2
From Tn ∈ Forb(T1 , . . . , Tn−1 ), n > 1, we can now deduce that T1 , T2 , . . . is abad sequence. (It is in fact a descending sequence, since each Tn is universal
in Gn .) This contradicts Nash-Williams’s theorem that the infinite trees are
well-quasi-ordered under rooted topological embedding, and thus completes
the proof of Theorem 1.

Concluding remarks Note that all the arguments used remain valid whenrestricting the class of trees to those trees every vertex of which has at mosttwo successors. Thus, there are uncountably many topological types of thesetrees already.
A problem that remains open is to find a constructive proof of Theorem 1.

References[1] R. Diestel, Graph Theory (3rd edition), Springer-Verlag, New York, 2005.
[2] H. van der Holst, Problem posed at the 2005 Graph Theory workshop at
Oberwolfach.
[3] D. Kühn, On well-quasi-ordering infinite trees – Nash-Williams’s theorem
revisited, Math. Proc. Camb. Phil. Soc. 130 (2001), 401–408.
[4] C.St.J.A. Nash-Williams, On well-quasi-ordering infinite trees, Proc. Camb. Phil.
Soc. 61 (1965), 697–720.

3