{'fraction_non_alphanumeric': 0.052502832886666545, 'fraction_numerical': 0.011025774772020073, 'mean_word_length': 3.1856508318903862, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
All graphs have tree-decompositions displaying their topological ends

We show that every connected graph has a spanning tree that displays all its topological ends. This proves a 1964 conjecture of Halin in corrected form, and settles a problem of Diestel from 1992.


Introduction
A major recent development in the theory of infinite graphs has to do with how to extend theorems about finite graphs and their cycles to infinite graphs, see for example [1,3,12,13,15,20], and [10] for a survey.
A key tool to extend these theorems are trees that encode the structure of the end boundary of (infinite) graphs. However, these trees were not available for all graphs so that people were only able to extend many such theorems to a subclass of all infinite graphs.
In this paper, we construct such trees for arbitrary graphs. This settles a more than 20 year old problem of Diestel. In [5], we demonstrate how these new trees can be used to extend theorems to arbitrary graphs: We prove that the topological cycles of any graph are the circuits of a matroid, which in general is neither finitary nor cofinitary and uncountable in a nontrivial way.
Throughout this paper, when we say end, we always mean vertex-end. The hope to display the structure of any graph together with its ends by a tree can be traced back to a paper of Halin from 1964 [16]: A rooted spanning tree of a graph G is end-faithful if for each end ω of G it contains precisely one ray belonging to ω and starting at the root. For example, every normal spanning tree is end-faithful. Halin conjectured that every graph has an end-faithful spanning tree. However, Seymour and Thomas [19], and independently Thomassen [22] found counterexamples. Nevertheless, our main result implies a weakening of Halin's conjecture, which is true for all graphs, as explained below.
More recently, in order to study infinite graphs, tree-decompositions of finite adhesion have been used, see for example [21], [18], [2]. Here the adhesion of a tree-decomposition is finite if any two adjacent parts intersect finitely. In [9,Problem 4.3], Reinhard Diestel wanted to know if for every graph G there is a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion that somehow encodes the structure of the graph with its ends.
Let us be more precise: Given an end ω, every finite order separation (A, B) has a unique side including a subray of every ray belonging to ω. We say that ω lives in that side. Thus we can direct every edge tu of T such that ω lives in A for the separation (A, B) corresponding to tu. For each end ω, this orientation of T points towards a node of T or to an end of T . We say that the end lives in the part for that node or that end, respectively.
Given a property P of ends, the ends of T are the ends of G with property P if in each end of T there lives a unique end and it has property P , and conversely each end of G with property P lives in some end of T . An end is thin if there do not exist infinitely many vertex disjoint rays belonging to that end.
Reinhard Diestel asked if every graph G has a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion such that the ends of T are the thin ends of G, and such that in each decomposition part there lives at most one end of G. Unfortunately, this is not true. In Example 3.1, we construct a graph G such that each of its tree-decompositions of finite adhesion has a part in which two ends of G live. Moreover, in Example 3.5, we construct a graph G that does not have a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion such that the ends of T are the thin ends of G. With these counterexamples in hand, the remaining question seems to be if there is a natural nontrivial property P such that every graph G has a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion such that the ends of T are the ends of G with property P . Our main result answers this in the affirmative. An end ω is dominated if there is a vertex v together with an infinite v-R-fan to every ray R belonging to ω. Theorem 1.1. Every graph G has a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion such that the ends of T are the undominated ends of G.
We cannot hope to get such a tree-decomposition with the additional property that for any two undominated ends, there is an edge of the tree whose corresponding adhesion set separates these ends in a minimal way, see Example 3.4. As the example of the 2-dimensional grid shows, we cannot hope to get a tree-decomposition as in Theorem 1.1 that is invariant under the group of automorphisms.
The tools we develop also allow us to answer the question to what extend the set of all ends of an infinite graph has a tree-like structure, see [4].
Like normal spanning trees, the tree-decompositions from Theorem 1.1 can be used to extend theorems about finite graphs but as the tree-decompositions unlike normal spanning trees exist for all graphs, they make it possible to extend these theorems to all infinite graphs. We demonstrate this in [5], where we prove that the topological cycles of an arbitrary graph are the circuits of a matroid, which in general is neither finitary nor cofinitary and uncountable in a nontrivial way.
Our main result also implies the following weakening of Halin's conjecture. A rooted spanning tree of a graph G is end-faithful for a set Ψ of ends if for each end ω ∈ Ψ it contains precisely one ray belonging to ω and starting at the root. Corollary 1.2. Let G be a graph and Ψ be its set of undominated ends. Then G has an end-faithful spanning tree for Ψ.
One might ask if it is possible to construct an end-faithful spanning tree for Ψ with the additional property that it does not include any ray to an end not in Ψ. However, this is not possible in general. Indeed, Seymour and Thomas constructed a graph G all of whose ends are dominated that does not have a rayless spanning tree [19]. This paper is organised as follows. We start in Section 2 by giving basic definitions. In Section 3, we give the examples mentioned in the Introduction. After summarising in Section 4 the preliminaries that are only relevant for Section 5, we prove in Section 5 that for every graph there is a nested set of separations distinguishing the set of the ends efficiently. In Section 6, we use this theorem to prove our main result, Theorem 1.1. We also deduce Corollary 1.2 from it. In [4], we use our newly developed tools to answer the question to what extend the set of all ends of an infinite graph has a tree-like structure.

Preliminaries
Throughout, notation and terminology for graphs are that of [11] unless defined differently. And G always denotes a graph. We denote the complement of a set X by X . For an edge set X, we denote by V (X), the set of vertices incident with edges from X. For a vertex set W , we denote by s W , the set of those edges with at least one endvertex in W .
For us, a separation is just an edge set. The boundary ∂(X) of a separation X is the set of those vertices adjacent with an edge from X and one from X . The order of X is the size of ∂(X). A separation X is componental if there is a component C of G − ∂(X) such that s C = X. Two separations X and Y are nested if one of the following 4 inclusions is true: , then it is incident with an edge from Y \ X and an edge from Y \ X. Thus if additionally, X and Y are nested, then either X ⊆ Y or Y ⊆ X . We shall refer to the four sets An end ω lives in a separation X of finite order if there is a component C of G − ∂(X) such that ω lives in C and s C ⊆ X.
A separation X of finite order distinguishes two ends ω and µ if one of them lives in X and the other in X . It distinguishes them efficiently if X has minimal order amongst all separations distinguishing ω and µ.
A tree-decomposition of G consists of a tree T together with a family of subgraphs (P t |t ∈ V (T )) of G such that every vertex and edge of G is in at least one of these subgraphs, and such that if v is a vertex of both P t and P w , then it is a vertex of each P u , where u lies on the v-w-path in T . Moreover, each edge of G is contained in precisely one P t . We call the subgraphs P t , the parts of the tree-decomposition. Sometimes, the "Moreover"-part is not part of the definition of tree-decomposition. However, both these two definitions give the same concept of tree-decomposition since any tree-decomposition without this additionally property can easily be changed to one with this property by deleting edges from the parts appropriately. Given a directed edge tu of T , the separation corresponding to tu is the set of those edges which are in parts P w , where u lies on the unique t-w-path in T . The following is well-known and has been explained in the Introduction. Lemma 2.1. Given a tree-decomposition (P t |t ∈ V (T )) of finite adhesion of a graph G, each end of G lives in a part or end of G. Moreover, in each end of T , there lives at most one end of G.

Example section
Throughout this section, we denote by T 2 the infinite rooted binary tree, whose nodes are the finite 0-1-sequences and whose ends are the infinite ones. In particular, its root is denoted by the empty sequence φ.
Example 3.1. In this example, we construct a graph G such that all its tree-decompositions of finite adhesion have a part in which two ends live. We obtain G from T 2 by adding a single vertex v ω for each of the continuum many ends ω of T 2 , which we join completely to the unique ray belonging to ω starting at the root. Note that the ends of G are the ends of T 2 . For a finite path P of T 2 starting at φ, we denote by A(P ), the set of those ends of G whose corresponding 0-1-sequence begins with the finite 0-1-sequence which is the last vertex of P .
Suppose for a contradiction that there is a tree-decomposition (T, P t |t ∈ V (T )) of G of finite adhesion such that in each of its parts lives at most one end.
Lemma 3.2. For each k ∈ N, there is a separation X k corresponding to a directed edge t k u k of T together with a finite path P k of T of length k starting at φ satisfying the following.

uncountably many ends of
Proof. We start the construction with picking P 0 = φ and X 0 such that uncountably many ends live in it. Assume that we already constructed for all i ≤ k separations X i and P i satisfying the above. Let Q k and R k be the two paths of T 2 starting at φ of length k + 1 extending P k . Then A(P k ) is a disjoint union of A(Q k ) and A(R k ). For P k+1 we pick one of these two paths of length k + 1 such that uncountably many ends of A(P k+1 ) live in X k ; Let S k be the component of T − t k containing u k . Let F k be the set of those directed edges of S k directed away from u k . Note that if some separation X corresponds to some ab ∈ F k , then X ⊆ X k . Actually, we will find t k+1 u k+1 in F k . We colour an edge of F k red if uncountably many ends of A(P k+1 ) live in the separation corresponding to that edge.
Suppose for a contradiction that there is a constant c such that for each r, there are at most c red edges of F k with distance r from t k u k in T . Let W be the subforest of T consisting of the red edges. Note that W is a tree with at most c ends. By construction, only countably many ends of A(P k+1 ) living in X k can live in parts of nodes not belonging to W or ends not belonging to W . As W itself has only countably many nodes and ends, two ends of A(P k+1 ) have to live in the same part or end. The second is not possible by Lemma 2.1. Thus we get a contradiction to the assumption that no two ends live in the same part P t .
Hence there is some distance r such that there are at least |∂(X k )|+1 red edges of F k with distance r from t k u k in T . Each end ω with v ω ∈ ∂(X k ) can live in at most one separation corresponding to one of these edges. Hence amongst these red edges we can pick t k+1 u k+1 such that no such ω lives in its corresponding separation X k+1 . Clearly, X k+1 and P k+1 have the desired properties, completing the construction. Lemma 3.3. Let X k and P k be as in Lemma 3.2. Then P k ⊆ V (X k ).
Proof. By 1, uncountably many ends of A(P k ) live in X k . Thus infinitely many of their corresponding vertices v ω are in V (X k ). Since only finitely many of these vertices can be in ∂(X k ), one of these vertices has all its incident edges in X k . Since P k is in its neighbourhood, it must be that P k ⊆ V (X k ).
Having proved Lemma 3.2 and Lemma 3.3, it remains to derive a contradiction from the existence of the X k and P k . By construction R = k∈N P k is ray. Let µ be its end. By Lemma 3.3, R ⊆ V (X k ) so that µ lives in each X k . Hence v µ ∈ V (X k ) for all k. Let e be any edge of G incident with v µ . As each edge of G is in precisely one part P t , the edge e is eventually not in X k . Hence v µ is eventually in ∂(X k ), contradicting 4 of Lemma 3.2. Hence there is no tree-decomposition (T, P t |t ∈ V (T )) of G of finite adhesion such that in each of its parts lives at most one end.
Example 3.4. In this example, we construct a graph G such that for any tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion that distinguishes the set of undominated ends, there are two undominated ends such that no separation corresponding to an edge of T distinguishes these two ends efficiently.
Given two graphs G and H, by G × H, we denote the graph with vertex set V (G) × V (H) where we join two vertices (g, h) and (g , h ) by an edge if both g = g and hh ∈ E(G) or both h = h and gg ∈ E(G). Given a set of natural numbers X, by X we denote the graph with vertex set X where two vertices are adjacent if they have distance 1.
We start the construction with the graph N * × {1, 2, 3}. Then for each k ∈ N * , we glue on the vertex set Let ω k be the end whose subrays are eventually in H k . Note that ω k is undominated. For k < m, the separator S k = ({1, ..., k} × {2}) + (k, 3) separates ω k from ω m and every other separator separating ω k from ω m has strictly larger order. Note that G − S k has precisely two components, one containing (1, 1) and the other containing (1,3). Thus every separation X with ∂(X) = S k has the property that precisely one of (1, 1) and (1, 3) is in V (X). Now let (T, P t |t ∈ V (T )) be a tree-decomposition of finite adhesion that distinguishes the set of undominated ends. Let P t be a part containing (1,1) and P u be a part containing (1,3). If X corresponds to an edge e of T and precisely one of (1, 1) and (1, 3) is in V (X), then e lies on the finite t-u-path in T . Thus there are only finitely many such X so that there is some k ∈ N * such that S k is not the separator of any X corresponding to an edge of T . Thus there are two undominated ends that are not distinguished efficiently by (T, P t |t ∈ V (T )).
Example 3.5. In this example, we construct a graph G that does not have a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion such that the thin ends of G are the ends of T . Let Γ be the set of those ends of T 2 whose 0-1-sequences are eventually constant and let ω 1 , ω 2 , . . . be an enumeration of Γ. We represent each end ω of T 2 by the unique ray R(ω) starting at the root and belonging to ω.
For n ∈ N * , let H n be the graph obtained by T 2 by deleting each ray R(ω i ) for each i ≤ n. We obtain G from T 2 by adding for each natural number n the graph H n where we join each vertex of T 2 with each of its clones in the graphs H n . Note that a vertex in R(ω n ) has at most n clones.
It is clear from this construction that T 2 is a subtree of G whose ends are those of G. For every end ω not in Γ, there are infinitely many vertex-disjoint rays in G belonging to ω, one in each H n . For ω n ∈ Γ and v ∈ R(ω n ), let S n (v) be the set of v and its clones. Each ray in G belonging to ω intersects the separators S n (v) eventually. Thus as |S n (v)| ≤ n, there are at most n vertex-disjoint rays belonging to ω n . Hence the thin ends of G are precisely those in Γ.
Suppose G has a tree-decomposition (T, P t |t ∈ V (T )) of finite adhesion such that the thin ends live in different ends of T . It remains to show that there is an end of T in which no end of Γ lives by Lemma 2.1. For that, we shall recursively construct a sequence of separations (A n |n ∈ N * ) that correspond to edges of T satisfying the following.

1.
A n+1 is a proper subset of A n ; 2. infinitely many ends of Γ live in A n but none of {ω 1 , . . . , ω n }.
We start the construction by picking an edge of T arbitrarily; one of the two separations corresponding to that edge satisfies 2 and we pick such a separation for A 1 . Now assume that we already constructed A 1 , . . . , A n satisfying 1 and 2. By assumption, there are two distinct ends α and β in Γ that live in A n . If possible, we pick β = ω n+1 . Since α and β live in different ends of T , there must be some separation A n+1 corresponding to an edge of T such that α lives in A n+1 but β does not.
We claim that A n+1 is a proper subset of A n . Indeed, A n+1 and A n are nested and as α lives in both of them, either A n ⊆ A n+1 or A n+1 ⊆ A n . Since β witnesses that the first cannot happen, it must be that A n+1 is a proper subset of A n .
Having seen that A n+1 satisfies 1, note that it also satisfies 2 since by construction one end of Γ lives in A n+1 , which entails that infinitely many ends of Γ live in A n+1 because for each finite separator S of G, each infinite component of G − S contains infinitely many ends from Γ.
Having constructed the sequence of separations (A n |n ∈ N * ) as above, let e n be the edge of T to which A n corresponds. The set of the edges e n lies on a ray of T but no end in Γ lives in the end of that ray by 2, completing this example.

Preparing for Section 5
In this section, we summarize the necessary background in order to read Section 5.

Profiles
For two separations X and Y , we denote by L(X, Y ) the intersection of there may be vertices in L(X, Y ) that only have neighbours in X \ Y and Y \ X so that they are not in ∂(X ∩ Y ).
Profiles are slightly more general objects than tangles, which are a central concept in Graph Minor Theory [6]. Reader familiar with tangles will not miss a lot if they just think of tangles instead of profiles. In fact, they can even skip the definition of robustness of a profile below as tangles are always robust.
Definition 4.2. A profile P of order k + 1 is a set of separations of order at most k satisfying the following.
Note that (P1) implies that ∅ ∈ P . Under the presence of (P0) the axiom (P1) is equivalent to the following: if X ∈ P and X ⊆ Y with ∂(Y ) ≤ k, then Y ∈ P . Every tangle of order k + 1 induces a profile of order k + 1, where a separation X of order at most k is in the induced profile if and only if the tangle says that it is the big side (formally, this means that X is not in the tangle). However, there are profiles of order k + 1 that do not come from tangles, see [7,Section 6]. So far profiles have only been defined for finite graph [6], and for them the definition given here is equivalent to one in [6]. Indeed, for finite graphs, there is an easy induction argument which proves (P3) from the other axioms. In infinite graphs, we get a different notion of profile if we do not require (P3) -for example if we leave out (P3), there is a profiles of order 3 on the infinite star.
A separation X distinguishes two profiles P and Q if X ∈ P and X ∈ Q or vice versa: X ∈ Q and X ∈ P . It distinguishes them efficiently if X has minimal order amongst all separations distinguishing P and Q. Given r ∈ N ∪ {∞} and k ∈ N, a profile P of order k + 1 is r-robust if there does not exist a separation X of order at most r together with a separation Y of order at most k such that L(X, Y ) < k and L(X , Y ) < k and Y ∈ P but both Y \ X and Y \ X are not in P . Note that every profile of order k + 1 is r-robust for every r ≤ k.
The notion of a profile is closely related to the well-known notion of a haven, defined next. Two subgraph of an ambient graph touch if they share a vertex or there is an edge of the ambient graph connecting a vertex from the first subgraph with a vertex from the second one. A vertex touches if the subgraph just consisting of that vertex touches. A haven of order k + 1 consists of a choice of a component of G − S for each separator S of size at most k such that any two of these chosen components touch. Note that if a component C is a component of both G − S and G − T for separators of order at most k, then it is in the haven for S if and only if it is in haven for T . Hence we can just say that a component is in a haven without specifying a particular separator.
Given a profile P of order k + 1, for each separator S of order at most k, there is a unique component C of G − S such that s C ∈ P by (P1) and (P3). By (P1), the collection of these components is a haven of order k + 1. We say that this haven is induced by P . A haven of order k + 1 is good if for any two separators S and T of size at most k and the components C and D of G − S and G − T that are in the haven, the set C ∩ D is also in the haven as soon as there are at most k vertices in S ∪ T that touch both C and D. In [4], we explain the connection between ends, havens and profiles.

Blocks of nested sets of separations
An N -block is a maximal set of vertices no two of which are separated by a separation in N . A separation X ∈ N distinguishes two N -blocks B and D if there are vertices in B \ ∂(X) and D \ ∂(X). Note that if B and D are different N -blocks, then there is some X ∈ N distinguishing them.
Lemma 4.5. Let k ∈ N, and let N be a nested set of separations of order at most k. Furthermore, let W be a set of at least k + 1 vertices no two of which are separated by a separation in N . Then there is a unique N -block B including W .
Proof. For every separation X ∈ N , there is one vertex v X of W that is not in ∂(X). Then B consists of precisely those vertices that for all X ∈ N are not separated by X from v X .
Usually torsos are just defined for parts of tree-decompositions [11]. We shall need the notion of a torso for any N -block of any nested set N . Unfortunately, this notion is not only more general but also more technical: Let N be a nested set of separations and B an N -block. For each X ∈ N , either The torso G T [B] is the multigraph with vertex set B whose edge set is obtained from E(B) by adding for each X ∈ N a complete graph H X on It remains to consider the case that all edges incident with v are in X .
Let N be a nested set of separations, B an N -block and H a haven of order k + 1 that lives in B, that is for every separator S of order at most k and every component For a profile P of order k + 1, the set P B consists of those separations X of order at most k in G T [B] such thatX ∈ P . Lemma 4.9. Let N be a nested set of separations and B be an N -block such that B ⊆ V (X) for every X ∈ N . Let P be a profile in G of order k + 1 such that X / ∈ P for every X ∈ N .
Proof. The haven induced by P induces a good haven in the graph G T [B]. By Remark 4.4, this haven is induced by a profile, which is equal to P B . Hence P B is a profile of order k + 1.
To see the "Moreover"-part, first note that L(X, Y ) ≥ L(X,Ỹ ). Thus if X and Y witness that P B is not r-robust, thenX andỸ witness that P is not r-robust, completing the proof.
Moreover, P B and Q B are r-robust profiles of order at least l + 1, which Lemma 4.5. We may assume that Y ∈ P but Y ∈ Q.  By exchanging the roles of B and D if necessary, we get that there is some Z ∈ N such that there is some v ∈ B all of whose incident edges are in Z, and some w ∈ D all of whose incident edges are in Z . As B and D are N -inseparable, it must be that B ⊆ V (Z), and D ⊆ V (Z ). Note that By the strengthening of the "Moreover"-part we have proved, either Z ⊆X orX ⊆ Z, as well as, either Z ⊆Ỹ orỸ ⊆ Z . We will finish by checking that in all these four caseX andỸ are nested.

Miscellaneous
Lemma 4.12. Let X and Y be two separations such that there is a component C of G − ∂(X) with s C = X and C does not intersect ∂(Y ). Then X and Y are nested.
Proof. By the definition of nestedness, it suffices to show that X ⊆ Y or X ⊆ Y . For that, by symmetry, it suffices to show that if there is some edge e 1 ∈ X ∩ Y , then any other edge e 2 of X must also be in Y . For that note that e 1 has an endvertex v in C and that there is a path P included in C from v to some endvertex of e 2 . As no vertex of P is in ∂(Y ) and e 1 ∈ Y it must be that e 2 ∈ Y , as desired.
Lemma 4.13. Let X, Y and Z be separations such that first X and Y are not nested and second X ∩ Y and Z are not nested. Then Z is not nested with X or Y .
Proof. Recall that if A and Z are nested, then one of Suppose for a contradiction that X ∩ Y is not nested with Z but X and Y are. By exchanging the roles of X and Y if necessary, we may assume by the above that X ⊆ Z and Y ⊆ Z . Then X ⊆ Y , contradicting the assumption that X and Y are not nested.
Lemma 4.14. Let X be a separation of order k. Let Y be a tight separation such that G − ∂(Y ) has at least k + 1 components. Then one of the links Then v and w are in the neighbourhood of every component C of G − ∂(Y ). Thus there are k + 1 internally disjoint paths from v to w, contradiction that fact that ∂(X) separates v from w.

Nested sets of separations
The aim in this section is to construct a nested set of separations of finite order that distinguishes any two ends efficiently, which is needed in the proof of Theorem 1.1. Related results are proved in [8] and [14]. Actually, we shall prove the stronger statement that for each r ∈ N ∪ {∞} there is a nested set N of separations that distinguishes any two r-robust profiles efficiently.
Overview of the proof We shall construct the set N as an ascending union of sets N k one for each k ∈ N, where N k is a nested set of separations of order at most k distinguishing efficiently any two r-robust profiles of order k + 1. Any two r-robust profiles of order k + 2 that are not distinguished by N k will live in the same N k -block. We obtain N k+1 from N k by adding for each N k -block a nested setÑ k+1 (B) that distinguishes efficiently any two r-robust profiles of order k + 2 living in B. Working in the torsos G T [B] will ensure that the setsÑ k+1 (B) for different blocks B will be nested with each other.
Summing up, we are left with the task of finding in these torso graphs G T [B] a nested set distinguishing efficiently all r-robust profiles of order k + 2. Theorem 5.2 deals with this problem if G T [B] is "nice enough". In order to make all torso graphs nice enough, we add in an additional step in which we enlarge N k a little bit so that for the larger nested set the new torso graphs are the old ones with the junk cut off. Lemma 5.1 will be the main lemma we use to enlarge N k .
Finishing the overview, we first state Lemma 5.1 and Theorem 5.2 and introduce the necessary definitions for that.
For any r-robust profile P and k ∈ N, the restriction P k of P to the set of separations of order at k is an r-robust profile, whose order is the minimum of k + 1 and the order of P . An r-profile set is a set of r-robust profiles such that if P ∈ P then for each k ∈ N the restriction P k is in P. Until the end of Subsection 5.2, let us a fix a graph G together numbers k, r ∈ N ∪ {∞} with k ≤ r and an r-profile set P.
A set N of nested sets is r-extendable (for P) if for any two distinct profiles in P of the same order, there is some separation X nested with N that distinguishes these two profiles efficiently.
By R(k, r, P, G) we denote the set of those separations whose order is finite and at most k that distinguish efficiently two r-robust profiles in P in the graph G. It may happen for some X ∈ R(k, r, P) that G − ∂(X) has a component C such that ∂(s C ) is a proper subset of ∂(X). By S(k, r, P, G), we denote the set of all separations s C for such components C of G − ∂(X) for some X ∈ R(k, r, P) in the graph G. If it is clear from the context what G is, we shall just write R(k, r, P) or S(k, r, P), or even just R(k, r) or S(k, r).
A separation X strongly disqualifies a set Y if |∂(Y )| is strictly larger than both |L(X, Y )| and |L(X , Y )|. A set X disqualifies a set Y if it strongly disqualifies Y or Y . Recall that a separation X is tight if ∂(s C ) = ∂(X) for every component C of G − ∂(X). Note that every X ∈ R(k, r) is tight if and only if S(k, r) = ∅.
Theorem 5.2. Let k ∈ N and r ∈ N ∪ {∞} with k ≤ r. Assume that S(k, r) = ∅. Any set N of nested tight separations of order at most k that are not disqualified by any X ∈ R(r, r) is r-extendable. If N is a maximal such set, then it distinguishes any two r-robust profiles of order k + 1 in P.

Proof of Lemma 5.1.
Lemma 5.3. If X distinguishes two r-robust profiles P 1 and P 2 efficiently, then X is not disqualified by any separation Y with ∂(Y ) ≤ r.
Proof. We may assume that X ∈ P 1 and X ∈ P 2 . Suppose for a contradiction that Y strongly disqualifies X. Then |L(X, Y )| < |∂(X)| and |L(X, Y )| < |∂(X)|. As neither X ∩ Y nor X ∩ Y is in P 2 , these two sets cannot be in P 1 either since X distinguishes P 1 and P 2 efficiently. This contradicts the assumption that P 1 is r-robust. Similarly, one shows that Y cannot strongly disqualify X , and thus Y does not disqualify X.

Lemma 5.4. Let X and Y be two separations distinguishing profiles in
Proof. Let P and P be two profiles in P distinguished efficiently by X, where X ∈ P .
Sublemma 5.5. G − ∂(X) has two components D and K different from C such that s D ∈ P and s K ∈ P .
Proof. s C can be in at most one of P and P . By the efficiency of X it actually cannot be in precisely one of them. Thus s C is in none of them. Hence the components D and K of G−∂(X) such that s D ∈ P and s K ∈ P , which exist by (P3), are different from C.
Let Q and Q be two profiles in P distinguished efficiently by Y , where Y ∈ Q. Since |∂(X)| ≤ |∂(Y )|, we have X ∈ Q or X ∈ Q. By exchanging the roles of X and X if necessary, we may assume that X ∈ Q. By Sublemma 5.5, we may assume that s C ⊆ X by replacing X by X ∪ s C if necessary. Proof. First we consider the case that |L(X, Y )| ≤ |∂(Y )| and X ∩ Y ∈ Q. By (P3), there is a component F of G − ∂(Y ∩ X) such that s F ∈ Q. By the efficiency of Y , it must be that ∂(s F ) = ∂(Y ∩ X) as s F distinguishes Q and Q . Thus the union F of F and the link ∂(Y ) \ V (X ) is connected.
Suppose for a contradiction that both C and D meet ∂(Y ), then they both meet ∂(Y ) in vertices of the link ∂(Y ) \ V (X ). Since C and D are components, they both must contain F , and hence are equal, which is the desired contradiction. Thus at most one of C and D can meet ∂(Y ).
By Sublemma 5.6 it remains to consider the case where |L(X, Y )| ≤ |∂(Y )| and X ∩Y ∈ Q , which is dealt with analogous to the above case.
Recall that ∂(s C ) ⊆ ∂(s D ). By Sublemma 5.7, one of the links ∂(s C ) \ V (Y ) and ∂(s C ) \ V (Y ) must be empty since otherwise there would a path joining these two links and avoiding ∂(Y ), which is impossible. By symmetry, we may assume that ∂(s C ) \ V (Y ) is empty. Thus ∂(Y \ s C ) ⊆ ∂(Y ). Since R(k − 1, r) = ∅, and s C ∈ P , it must be that s C / ∈ Q. Thus Y \ s C ∈ Q by (P2) so that Y \ s C distinguishes Q and Q . By the efficiency of Y , it must be that ∂(Y \ s C ) = ∂(Y ). Hence the link ∂(Y ) ∩ C is empty, as desired.
Proof of Lemma 5.1. Let X ∈ R(k, r) and Y ∈ R(r, r) of order at least k. Let C be a component of G − ∂(X) and D be a component of G − ∂(Y ). In order to see that S(k, r) is a nested, it suffices to show that for any such C and D that the separations s C and s D are nested. This is true by Lemma 5.4 and Lemma 4.12. In order to see that S(k, r) is an r-extendable, it suffices to show that for any such C and Y that the separations s C and Y are nested. This is true by Lemma 5.4 and Lemma 4.12, as well.

Proof of Theorem 5.2.
Before we prove Theorem 5.2, we need some intermediate lemmas. Throughout this subsection, we assume that S(k, r) is empty. Let U be the set of those tight separations of order at most k that are not disqualified by any X ∈ R(r, r). Note R(k, r) ⊆ U .
Lemma 5.8. For any componental separation X ∈ R(r, r), there are only finitely many Y ∈ U not nested with X.
Proof. First, we show that X is nested with every Y ∈ U such that the link ∂(X)\V (Y ) is empty. By Lemma 4.12, it suffices to show that ∂(Y )\V (X ) is empty. As X does not strongly disqualify Y , one of the links ∂(Y )\V (X) and ∂(Y )\V (X ) is empty. Hence we may assume that ∂(Y )\V (X) is empty. If Y is not nested with X, there must be a component of C of G − ∂(Y ) all of whose neighbours are in ∂(X) ∩ ∂(Y ). As Y is tight, it must be that is empty. Hence X and Y are nested by Lemma 4.12. Similarly one shows that X is nested with every Y ∈ U such that the link ∂(X) \ V (Y ) is empty.
It remains to show that there are only finitely many Y ∈ U not nested with X such that both links ∂(X)\V (Y ) and ∂(X)\V (Y ) are nonempty. By Lemma 4.15, there are only finitely many triples (v, w, T ) where v, w ∈ ∂(X) and T is a separator of size at most k separating v and w minimally. Since each ∂(Y ) for some Y as above is such a separator T , it suffices to show that there are only finitely many Z ∈ U with ∂(Z) = ∂(Y ). This is true as G − ∂(Y ) has at most ∂(X) + 1 components by Lemma 4.14.
Lemma 5.9. Let N be a nested subset of U . For any two distinct profiles P and Q in P of the same order that are not distinguished by any separation of order less than k, there is some separation X ∈ R(k, r) ⊆ U that is nested with N and distinguishes P and Q efficiently.
Proof. First, we show that there is some X ∈ U distinguishing P and Q efficiently that is nested with all but finitely many separations of N . Since S(k, r) is empty, R(k, r) is a subset of U . Thus U contains some separation A distinguishing P and Q efficiently. By (P3), we can pick such an A that is componental. By Lemma 5.8, A is nested with all but finitely many separations of N . Hence we can pick X distinguishing P and Q efficiently such that it is not nested with a minimal number of Y ∈ N .
Suppose for a contradiction that there is some Y ∈ N that is not nested with X. We may assume that Y does not distinguish P and Q since otherwise Y would distinguish P and Q efficiently. Thus either both Y ∈ P and Y ∈ Q or both Y ∈ P and Y ∈ Q. Since Y is nested with N , we may by symmetry assume that Y ∈ P and Y ∈ Q.
Since X does not strongly disqualify Y by the definition of U , either |L(X, Y )| ≥ |∂(Y )| or |L(X , Y )| ≥ |∂(Y )|. By symmetry, we may assume that |L(X, Y )| ≥ |∂(Y )|. By exchanging the roles of P and Q if necessary, we may assume that X ∈ P and X ∈ Q. By Remark 4.1, |L(X , Y )| ≤ |∂(X)|. Note that X ∩ Y / ∈ P as X / ∈ P by (P1) but X ∩ Y ∈ Q by (P2). Thus X ∩ Y distinguishes P and Q efficiently. Any separation in N not nested with X ∩ Y is by Lemma 4.13 not nested with X. As Y is nested with X ∩ Y , the separation X ∩ Y violates the minimality of X. Hence X is nested with N , completing the proof.
Proof of Theorem 5.2. By Lemma 5.9 any nested subset of U is r-extendable and any maximal nested subset of U distinguishes any two distinct profiles in P of order at k + 1.

Proof of the main result of this section.
In this subsection, we proof the following.
Theorem 5.10. For any graph G and any r ∈ N ∪ {∞}, there is a nested set of separation N that distinguishes efficiently any two r-robust profiles of the same order.
First we need an intermediate lemma, for which we fix some notation. Let us fix some r ∈ N ∪ {∞}, some finite k ≤ r and an r-profile set P. Let N be a nested set of separations of order at most k that is r-extendable for P together with for each N -block B, let N B be a nested set of separations of G T [B] of order at most k. Furthermore, we assume that N B is r-extendable for the set P(B) consisting of those r-robust profiles in G T [B] that have the form P B for some r-robust profile P of G. We abbreviate M = N ∪ Ñ B , where the union ranges over all N -blocks B.
Lemma 5.11. The set M is nested. If N distinguishes any two profiles of order l in P efficiently for every l ≤ k + 1, then M is r-extendable for P.
Proof. By definition any two X and Y in the same setÑ B are nested. Thus M is nested by Lemma 4.11.
It remains to show for every l ≥ k + 1 and any two profiles P and Q in P that are distinguished efficiently by a separation of order l that there is a separation nested with M that distinguishes P and Q efficiently. We may assume that P and Q both have order l + 1 as P is an r-profile set. By Proof of Theorem 5.10. We shall construct the nested set N of Theorem 5.10 as a nested union of sets N k one for each k ∈ N ∪ {−1}, where N k is a nested r-extendable set of separations of order at most k that distinguishes any two r-robust profiles efficiently that are distinguished by a separation of order at most k. We start the construction with N −1 = ∅. Assume that we already constructed N k with the above properties. For each N k -block B, we let P(B) be the set of those r-robust profiles in G T [B] that have the form P B for some r-robust profile P of G. Proof. Suppose for a contradiction, two profiles P B and Q B in P(B) can be distinguished by a separation X of order at most k. ThenX has order at most |∂(X)| by Lemma 4.6 and distinguishes the profiles P and Q which induce P B and Q B . So P and Q are distinguished by N k by the induction hypothesis. This contradicts the assumption that P and Q are both in P(B).
By Sublemma 5.12, we can apply Lemma 5.1 to G T [B] and P(B), yielding that the set S(k + 1, r, P(B)) is a nested r-extendable set of separations. For each S(k + 1, r, P(B), G T [B])-block B , we let P(B ) be the set of those r-robust profiles in G T [B ] that have the form P B for some r-robust profile P in P(B). Proof. Suppose for a contradiction, there is some X ∈ S(k+1, r, By Lemma 4.6 and the definition of P(B ), the separationỸ distinguishes efficiently two profiles in P(B) so that Y ∈ R(k + 1, r, P(B), G T [B]). By Lemma 4.6,Ỹ has order precisely k + 1 sinceỸ has order k + 1 because it distinguishes two profiles that are not distinguished by N k . HenceX ∈ S(k + 1, r, P(B), G T [B]) by Lemma 4.6. Thus X is the empty, which is the desired contradiction.
By Zorn's Lemma we pick a maximal set N (B ) of nested tight separations of order at most k in G T [B ] that are not disqualified by any X ∈ R(r, r, P(B ), G T [B ]). By Theorem 5.2 the set N (B ) is r-extendable and distinguishes any two r-robust profiles of order k + 2 in P(B ). In other words, N (B ) distinguishes any two r-robust profiles in P(B ) that can be distinguished by a separation of order k+1 since any two such profiles induce different r-robust profiles of order k + 2, which are also in P(B ).
Let  N k+1 (B) is a nested and r-extendable set of separation of order at most k + 1 in G T [B]. Let N k+1 be the union of the setsÑ k+1 (B) together with N k , where the union ranges over all N k -blocks B. Applying Lemma 5.11 again, we get that N k+1 is a nested and r-extendable set of separation of order at most k + 1 in G.
Sublemma 5.14. N k+1 distinguishes efficiently any two r-robust profiles P and Q of G that are distinguished by a separation of order at most k + 1.
Proof. We may assume that P and Q both have order k + 2. Let A distinguish P and Q efficiently. If A has order at most k, by the induction hypothesis, there is a separationÂ in N k distinguishing P and Q efficiently. SoÂ is in N k+1 by construction.
Otherwise there is a separation X distinguishing P and Q efficiently that is nested with N k as N k is r-extendable. By Lemma 4.10 and Remark 4.3, there is an N k -blocks B such that P B and Q B are r-robust profiles in G T [B] of order k + 2, which are distinguished efficiently by X B . Using the fact that N k+1 (B) is r-extendable and then applying Lemma 4.10 and Remark 4.3 again, we find an S(k + 1, r, P(B))-block B such that P B and Q B induce different r-robust profiles of order k + 2 in G T [B ], which are distinguished efficiently by some separation Z of order at most k + 1 by Remark 4.7. By construction, we find such a Z in N (B ). Applying Lemma 4.6 twice yields that the order ofZ is at most k +1. ThusZ distinguishes P and Q efficiently by definition of P B and Q B . AsZ is in N k+1 , this completes the proof.
Finally, the nested union N of the set N k is a nested set of separations that distinguishes efficiently any two r-robust profiles of the same order, as desired.
For an end ω, let P k ω be the set of those separations of order at most k, in which ω lives. It is straightforward to show that P k ω is an ∞-robust profile of order k + 1. Hence Theorem 5.10 has the following consequence.
Corollary 5.15. For any graph G, there is a nested set of separation N that distinguishes any two ends efficiently.

A tree-decomposition distinguishing the undominated ends
In this section, we prove Theorem 1.1 already mentioned in the Introduction.
A key lemma in the proof of Theorem 1.1 is the following.
Lemma 6.1. Let G be a graph with a finite nonempty set W of vertices. Then G has a star decomposition (S, Q s |s ∈ V (S)) of finite adhesion such that each undominated end lives in some Q s where s is a leaf. Moreover, only the central part Q c contains vertices of W , and for each leaf s, there lives an undominated end in Q s , and Q s \ Q c is connected.
Proof that Lemma 6.1 implies Theorem 1.1. We shall recursively construct a sequence T n = (T n , P n t |t ∈ V (T n )) of tree-decomposition of G of finite adhesion as follows. We starting by picking a vertex v of G arbitrarily and we obtain T 1 by applying Lemma 6.1 with W = {v}. Assume that we already constructed T n . For each leaf s of T n , we denote by W s the set of those vertices in Q s also contained in some other part of T n . Note that W s is contained in the part adjacent to Q s and thus is finite. By Lemma 6.1, we obtain a star decomposition T s of G[Q s ] such that no w ∈ W s is contained in a leaf part of T s and such that each undominated end living in Q s lives in a leaf of T s . We obtain T n+1 from T n by replacing each leaf part Q s by T s , which is well-defined as the set W s is contained in a unique part of T s .
By r, we denote the center of T 1 . For each j < m < n, the balls of radius j around r in T m and T n are the same. Thus we take T to be the tree whose nodes are those that are eventually a node of T n . For each t ∈ V (T ), the parts P n t are the same for n larger than the distance between t and r, and we take P t to be the limit of the P n t . It is easily proved by induction that each vertex in W s for s a leaf of T n has distance at least n − 1 from v in G. Thus for each j < n the ball of radius j around v in G is included in the union over all parts P n t where t is in the ball of radius j around r in T n . Hence (T, P t |t ∈ V (T )) is a tree-decomposition, and it has finite adhesion by construction.
It remains to show that the ends of T are the undominated ends of G, which is done in the following four sublemmas. Proof. There is a unique leaf s of T n such that ω lives in P n s . Let s n be the predecessor of s in T n . Then ω lives in the end of T to which s 1 s 2 . . . belongs. Sublemma 6.3. In each end τ of T , there lives an end of G.
Proof. For a directed paths P , we shall denote by ← − P the directed path with the inverse ordering of that of P .
Let s 1 s 2 ... be the ray in T starting at r that belongs to τ . By construction, the sets W s i are disjoint and finite. For each w ∈ W s i , we pick a path P w from w to v. Since W s i−1 separates w from v, there is a first w ∈ W s i−1 appearing on P w . Now we apply the Infinity Lemma in the form of [11,Section 8] on the graph whose vertex set is the disjoint union of the sets W s i , and we put in all the edges ww . Thus this graph has a ray w 1 w 2 ...
.. is an infinite walk with the property that the distance between v and a vertex k on K is at least n if k appears after ← − − P wn . In particular, K traverses each vertex only finitely many times. Thus K is a connected locally finite graph, and thus contains a ray R. Since R meets each of the sets W s i , the end to which R belongs lives in τ , as desired. Proof. Suppose for a contradiction, there are such ω 1 , ω 2 and τ . Let U be a finite separator separating ω 1 from ω 2 and let n be the maximal distances between v and a vertex in U . Then there is a leaf s of T n+1 such that τ lives in Q s . Let C i be the component of G − U in which ω i lives. Since W s separates U from Q s \ W s , it must be that the connected set Q s \ W s is contained in a component of G − U . As ω i lives in Q s \ W s by assumption, it must be that Q s \ W s ⊆ C i . Hence C 1 and C 2 intersect, which is the desired contradiction. Proof. Suppose for a contradiction u does. Let n be the distance between u and v in G. Then there is a leaf s of T n+1 such that ω lives in Q s . Thus the finite set W s separates u from ω, contradicting the assumption that u dominates ω. Sublemma 6.2, Sublemma 6.3, Sublemma 6.4 and Sublemma 6.5 imply that the ends of T are the undominated ends of G, as desired.
Remark 6.6. Let (T, ≤) be the tree order on T as in the proof of Theorem 1.1 where the root r is the smallest element. We remark that we constructed (T, ≤) such that (T, P t |t ∈ V (T )) has the following additional property: For each edge tu with t ≤ u, the vertex set w≥u V (P w ) \ V (P t ) is connected.
Moreover, we construct (T, P t |t ∈ V (T )) such that if st and tu are edges of T with s ≤ t ≤ u, then V (P s ) ∩ V (P t ) and V (P t ) ∩ V (P u ) are disjoint.
In order to prove Lemma 6.1, we need the following. Lemma 6.7. Let G be a connected graph and W ⊆ V (G) finite and nonempty. Then there is a set X of disjoint edge sets X of finite boundary such that every end not dominated by some w ∈ W lives in some X ∈ X and no edge e in any X ∈ X is incident with a vertex of W .
Proof that Lemma 6.7 implies Lemma 6.1. We may assume that G in Lemma 6.1 is connected.
Let Q be the union over X of the sets Q X . Let R be the set of those H in Q such that some undominated end lives in V (H). Note that each undominated end lives in some R ∈ R and that W does not intersect any such R. We obtain C from C by adding the vertex sets of all H ∈ Q \ R. We consider S = R ∪ {C } as a star with center C . It is straightforward to verify that (S, s|s ∈ V (S)) is a star decomposition with the desired properties.
The rest of this section is devoted to the proof of Lemma 6.7. We shall need the following lemma. Lemma 6.8. Let G be a connected graph and W ⊆ V (G) finite. There is a nested set N of nonempty separations of finite order such that every end not dominated by some w ∈ W lives in some X ∈ N and no edge e in any X ∈ N is incident with a vertex of W .
Moreover, if X, Y ∈ N are distinct with X ⊆ Y , then the order of Y is strictly larger than the order of X.
Proof. We obtain G W from G by first deleting W and then adding a copy of K ω , the complete graph on countably many vertices, which we join completely to the neighbourhood of W . Applying Corollary 5.15 to G W , we obtain a nested set N of separations of finite order such that any two ends of G W are distinguished efficiently by a separation in N . Let τ be the end to which the rays of the newly added copy of K ω belong. Let N consist of those separations in N that distinguish τ efficiently from some other end. As the separations in N distinguish efficiency, no X ∈ N contains an edge incident with a vertex of the newly added copy of K ω .
Given k ∈ N, a k-sequence (X α |α ∈ γ) (for N ) is an ordinal indexed sequence of elements of N of order at most k such that if α < β, then X α ⊆ X β . We obtain N from N by adding α∈γ X α for all k-sequences (X α ) for all k. Clearly, N ⊆ N and N is nested. Given k ∈ N, the set N k consists of those X ∈ N of order at most k, and N k consists of the inclusion-wise maximal elements of N k .
We let N = k∈N N k . By construction, each X ∈ N contains no edge incident with a vertex of the newly added copy of K ω , and thus it can be considered as an edge set of G, whose boundary is the same as the boundary in G W . We claim that N has all the properties stated in Lemma 6.8: By construction, each X ∈ N is nonempty. Since N ⊆ N , the set N is nested. The "Moreover"-part is clear by construction. Thus it remains to show that each end ω of G not dominated by some vertex in W lives in some element of N .
Let R be a ray belonging to ω. Since ω is not dominated by any vertex in W , for each w ∈ W there is a finite vertex set S w separating a subray R w of R from w. Then S = w∈W S w \ W separates R = w∈W R w from W in G but also in G W . Let ω be the end of G W to which R belongs. Note that S witnesses that ω = τ . Thus there is some X ∈ N in which ω lives. Let k be the order of X. By Zorn's lemma, N contains an inclusion-wise maximal element X of order at most k including X. By construction X is in N k and includes a subray of R . Thus ω lives in X , which completes the proof.
Next we show how Lemma 6.8 implies Lemma 6.7. A good candidate for X in Lemma 6.7 might be the inclusion-wise maximal elements of N . However, there might be an infinite strictly increasing sequence of members in N , whose orders are also strictly increasing, so that we cannot expect that the union over the members of this sequence has finite order, and hence cannot be in N . Thus we have to make a more sophisticated choice for X than just taking the maximal members of N . Lemma 6.8 implies Lemma 6.7. Let N be as in Lemma 6.8. Let X ∈ N be such that there is another Y ∈ N with X ⊆ Y , then the order of Y is strictly larger than the order of X. We denote the set of such Y of minimal order by D(X). Let H be the digraph with vertex set N where we put in the directed edge XY if Y ∈ D(X). A connected component of H, is a connected component of the underlying graph of H. Sublemma 6.9. Let X , Y ∈ N . Then X ⊆ Y if and only if there is a directed path from X to Y . Moreover, if X, Y ∈ N are not joined by a directed path, then they are disjoint.
Proof. Clearly, if there is a directed path from X to Y , then X ⊆ Y . Conversely, let X , Y ∈ N with X ⊆ Y . Let (X n ) be a sequence of distinct separations in N such that X ⊆ X 1 ⊆ ... ⊆ X n ⊆ Y . By Lemma 6.8, n ≤ |∂(Y )| − |∂(X )| + 1. Thus there is a maximal such chain (Z n ), which satisfies Z 1 = X and Z n = Y and X i+1 ∈ D(X i ) for all i between 1 and n − 1. Hence Z 1 ...Z n is a path from X to Y .
To see that "Moreover"-part, let X, Y ∈ N . As G is connected, there is an edge e incident with some vertex in W . Since e is not in X ∪ Y and X and Y are nested, X and Y must be disjoint if they are not joined by a directed path. Sublemma 6.10. Each vertex v of H has out-degree at most 1 Proof. Suppose for a contradiction v has out-degree at least 2. Then there are distinct X, Y ∈ D(v) so that neither X ⊆ Y nor Y ⊆ X. Thus X and Y are disjoint by Sublemma 6.9. Since v ⊆ X ∩ Y , this is the desired contradiction. Sublemma 6.11. Any undirected path P joining two vertices v and w contains a vertex u such that vP u and wP u are directed paths which are directed towards u.
Proof. It suffices to show that P contains at most one vertex of out-degree 0 on P . If it contained two such vertices then between them would be a vertex of out-degree 2, which is impossible by Sublemma 6.10.
We define X as the union of sets X C , one for each component C of H. The X C are defined as follows: If C has a vertex v C of out-degree 0, then by Sublemma 6.11 it cannot contain a second such vertex and for any other vertex v in C, there is a directed path from v to v C directed towards v C .
Hence v C includes any other v ∈ V (C). We let X C = {v C }.
Otherwise, C includes a ray X 1 X 2 . . . as C cannot contain a directed cycle by Sublemma 6.9. In this case, we take X C to be the set consisting of the Y i = X i \ X i−1 for each i ∈ N. Note that the order of Y i is bounded by the sum of the orders of X i and X i−1 , and thus finite.
Since no Y ∈ N contains an edge incident with some w ∈ W , the same is true for any Y ∈ X . Any two distinct X, Y ∈ X are disjoint: If X and Y are in the same X C , this is clear by construction. Otherwise it follows from the definition of Y i and Sublemma 6.9. Thus it remains to prove the following: Sublemma 6.12. Each end ω not dominated by some vertex of W lives in some X ∈ X .
Proof. By Lemma 6.8, there is some Z ∈ N in which ω lives. Let C be the component of H containing Z. If X C = {v C }, then Z ⊆ v C . Otherwise let the X i and the Y i be as in the construction of X C . If Z = X j for some j. Then we pick j minimal such that ω lives in X j . Since ω does not live in X j−1 , it must live in Y j , as desired.
Thus we may assume that Z is not equal to any X j . Let P be a path joining Z and X 1 = Y 1 . By Sublemma 6.11, P contains a vertex u such that ZP u and X 1 P u are directed paths which are directed towards u. If u = X 1 , then Z ⊆ Y 1 , and we are done. Otherwise X 1 P u is a subpath of the ray X 1 X 2 . . . since the out-degree is at most 1 so that u = X j for some j.
We pick P such that the j with u = X j is minimal and have the aim to prove that then Z ⊆ Y j . Since Z ⊆ X j , it remains to show that Z and X j−1 are disjoint. Suppose for a contradiction, there is a directed path Q joining Z and X j−1 . If Q is directed towards Z, then Z = X m for some m, contrary to our assumption. Thus Q is directed towards X j−1 . But then ZQX j−1 P X 1 has a smaller j-value, which contradicts the minimality of P . Hence there cannot be such a Q, and thus Z and X j−1 are disjoint by Sublemma 6.9. Having shown that Z ⊆ Y j , we finish the proof by concluding that then ω also lives in Y j .
We finish this section with the following corollary of Theorem 1.1.
Proof that Theorem 1.1 implies Corollary 1.2. By Theorem 1.1, G has a treedecomposition (T, P t |t ∈ V (T )) of finite adhesion such that the ends of T are the undominated ends of T , and we choose this tree-decomposition as in Remark 6.6. In particular, we can pick a root r of T such that for each edge tu with t ≤ u, the vertex set w≥u V (P w ) \ V (P t ) is connected.
Thus for each such edge tu, there is a finite connected subgraph S u of G[ w≥u V (P w )] that contains V (P t )∩V (P u ). Let Q t be a maximal subforest of the union of the S u , where the union ranges over all upper neighbours u of t. We recursively build a maximal subset U of V (T ) such that if a, b ∈ U , then Q a and Q b are vertex-disjoint. In this construction, we first add the nodes of T with smaller distance from the root. This ensures by the "Moreover"-part of Remark 6.6 that U contains infinitely many nodes of each ray of T .
Let S be the union of those S t with t ∈ U . We obtain S by extending S to a spanning tree of G, and rooting it at some v ∈ V (S) arbitrarily. By the Star-Comb-Lemma [11,Section 8], each spanning tree of G contains for each undominated end ω a ray belonging to ω.
Thus it remains to show that S does not contain two disjoint rays R 1 and R 2 that both belong to the same undominated end ω of G. Suppose there are such R 1 , R 2 and ω. Let t 1 t 2 . . . be the ray of T in which ω lives. Let n be so large that both R 1 and R 2 meet P tn . Then for each m ≥ n, the set S tm contains a path joining R 1 and R 2 . Thus the set Q t m−1 contains such a path. Since Q t m−1 ⊆ S for infinitely many m, the tree S contains a cycle, which is the desired contradiction.