The End Structure of a Graph: Recent Results and Open Problems

Reinhard Diestel

This paper aims to give a brief introduction to a set of problems, old and new, concerned with one of the main and long-standing quests in infinite graph theory: how to represent the end structure of a given graph by that of a simpler subgraph, in particular a spanning tree. There has been a fair amount of activity in this field recently; we describe the latest results, as well as some of the new problems which these results suggest.

1. Introduction

Let G be an infinite graph. A ray in G is a 1-way infinite path in G. An infinite connected subgraph of a ray R ⊂ G is called a tail of R. If S ⊂ V (G) is finite, the infinite component of R − S will be called the tail of R in G − S.

The following assertions are equivalent for rays P, Q ⊂ G:

(i) There exists a ray R ⊂ G which meets each of P and Q infinitely often.

(ii) For every finite S ⊂ V (G), the tails of P and Q in G − S lie in the same component of G −

S. (iii) G contains infinitely many disjoint paths between P and Q. If two rays P, Q ⊂ G satisfy (i)–(iii), we call them end-equivalent (or briefly equivalent) in G. An end of G is an equivalence class under this relation, and Ω(G) denotes the set of ends of G. If an end contains infinitely many disjoint rays, it is called thick; otherwise it is thin. A graph which has exactly one end is one-ended. For example, the 2-way infinite ladder has two thin ends, the infinite grid ℤ × ℤ and every infinite complete graph are one-ended graphs whose end is thick, and the dyadic tree has 2^{ℵ_{0}} thin ends.

The concept of an end was first introduced in the 1940s by Hopf [ 11 ] and Freudenthal [ 7 ], who essentially considered the ends of Cayley graphs in order to study discrete groups. This approach, which provides one of the main links between graph theory and algebra, remains the most important source of problems concerning ends; see Imrich and Seifter [ 12 ] for further references.

In 1964, the notion of an end was reintroduced by Halin [ 8 ], independently of [ 11 ] and [ 7 ]. Halin’s concern was purely graph theoretic, and one of the problems he raised was what this article is about: how can the end pattern of a given graph G be captured by a simple substructure of G, say by a spanning tree?

In order to make this precise (at least in one possible way—we shall see another later), consider a subgraph H of G. If P and Q are end-equivalent rays in H, then clearly P and Q are also equivalent in G. We therefore have a natural map η : Ω(H) → Ω(G) mapping each end of H to the end of G containing it as a subset. H will be called end-faithful in G if η is both 1–1 and onto. For example, the half grid ℕ × ℤ is end-faithful in the full grid ℤ × ℤ, but the ladder { 0, 1 } × ℤ is not. The dyadic tree has no proper end-faithful connected subgraph.

According to the above definition, the simplest kind of an end-faithful subgraph H ⊂ G would be one in which each end of G was represented by a unique ray in H. Strictly speaking, this is of course impossible: if R ⊂ H is a ray belonging to the end ω ^{∈} Ω(G), say, then so is every ray in H that has a tail in R, in particular every tail of R itself. (Note that a tail of R is trivially end-equivalent to R.) However, this is the only unavoidable ambiguity. For sharing a tail is clearly again an equivalence relation for rays (a refinement of end-equivalence), and up to this equivalence on the rays of H, uniqueness of representation may indeed be possible: if H is an end-faithful forest in G, then any two rays in H representing the same end ω of G have a common tail, so ω is represented in H by rays of a unique (tail equivalence) type.

Thus, if we interpret the desired simplicity of H as containing as few rays from each end of G as possible, then asking for an end-faithful forest in a graph is the strongest variant of the abovementioned general problem:

Problem 1.1. Does every graph contain an end-faithful forest?

The problem which Halin [ 8 ] originally adressed, and which has since been studied by various authors (see below), is an even stronger version of Problem 1.1: does every connected graph have an end-faithful spanning tree?

The next two sections give a survey of the known results on the existence of end-faithful spanning trees. In Section 4, we take a look at tree-decompositions of a graph, and consider the relationship between its own ends and those of its decomposition trees. In Section 5, finally, we introduce a natural topology on the end set Ω(G) (this was already considered by Hopf and Freudenthal), which will give Problem 1.1 an additional topological slant.

2. End-faithful spanning trees

Let us restate Halin’s original end problem:

Problem. (Halin, 1964) Does every connected graph have an end-faithful spanning tree?

Before we consider the problem itself, let us show that asking for an end-faithful spanning tree is no more restrictive, in the general case, than asking for an arbitrary end-faithful tree:

Proposition 2.1. If every connected graph contains an end-faithful tree, then every connected graph has an end-faithful spanning tree.

Proof. Suppose that every connected graph contains an end-faithful tree, and let G be any connected graph. We show that G has an end-faithful spanning tree.

Let { R(v) | v ^{∈} V (G) } be a set of disjoint rays, one for each vertex of G, so that R(v) meets G in precisely its initial vertex v. Let

G′ := G ∪ ⋃ { R(v) | v ^{∈} V (G) } ,

let T′ be any end-faithful tree in G′, and set T := T′ ∩ G. Note that any ray in T′ which is equivalent to R(v) must have a tail in R(v). Since T′ contains such a ray for each v (because it is end-faithful in G′) and since T′ is connected, T′ must contain every v, and T′ ∩ G = T must be connected. Thus, T is a spanning tree of G. Using the assumption that T′ is end-faithful in G′, it is easy to check that T is end-faithful in G. □

It is not difficult to find examples of spanning trees which are not end-faithful. The 2-way infinite ladder, for instance, has a spanning tree with 4 ends, two for each end of the ladder. (Consider its two sides together with one rung.) Here, η would not be 1–1. An infinite complete graph, on the other hand, can be spanned by a star, which has no ends at all; here, η would fail to be onto. Graphs in which every spanning tree is end-faithful do exist, but they have a very limited structure (see Section 4).

The first positive result on the existence of end-faithful spanning trees was already obtained by Halin [ 8 ]; for the convenience of the reader we sketch a proof.

Theorem 2.2. Every countable connected graph has an end-faithful spanning tree.

Proof. Let G be a countable connected graph, with vertex set { v_{i} | i ^{∈} ℕ } say. Starting with T_{0} := { v_{0} }, we construct a nested sequence T_{0}, T_{1}, T_{2}, … of finite subtrees of G, whose union will be an end-faithful spanning tree of G. Suppose T_{0}, …, T_{n−1} have been defined, and let i(n) := min{ i | v_{i} /^{∈} V (T_{n−1}) }. Let P_{n} = x_{n} … v_{i(n)} be a path in G with V (P_{n})∩V (T_{n−1}) = { x_{n} }, chosen so that x_{n} has maximum distance d(x_{n}, v_{0}) in T_{n−1} from v_{0}. Set T_{n} := T_{n−1} ∪ P_{n} and, eventually, T := ⋃_{n^{∈}ℕ} T_{n}.

T is clearly a spanning tree of G; let us show that the corresponding map η is 1–1. Suppose not, and let R, Q ⊂ T be rays which are equivalent in G but not equivalent in T. Then R and Q have disjoint tails; keeping these tails but maybe changing the rays’ initial segments we may assume that both R and Q have v_{0} as their initial vertex. Writing R = r_{0}r_{1} … and Q = q_{0}q_{1} …, let k := max { i | r_{i} = q_{i} } and put r_{k} = q_{k} =: x. Let n_{r}, n_{q} ^{∈} ℕ be such that P_{n_{r}} and P_{n_{q}} are the paths containing the edges xr_{k+1} and xq_{k+1}, respectively (Fig. 1).

FIGURE 1.

Note that n_{r} ≠ n_{q}, because each of the paths P_{n} can be extended to a path in T that ends in v_{0}, but no path containing both xr_{k+1} and xq_{k+1} can be so extended. Assume that n_{r} < n_{q}; then x = x_{n_{q}}. Let m ⩾ k + 1 be maximal with r_{m} ^{∈} T_{n_{q}−1}, and let U be an R–Q path which avoids T_{n_{q}−1} (using the end-equivalence of R and Q). Then

H := (P_{n_{q}} ∪ Q ∪ U ∪ R) ∖ (T_{n_{q}−1} − r_{m})

is a connected subgraph of G whose only vertex in T_{n_{q}−1} is r_{m}. H contains a v_{i(n_{q})}–T_{n_{q}−1} path with endvertex r_{m}; since r_{m} has greater distance from v_{0} in T_{n_{q}−1} than x, this contradicts the choice of P_{n_{q}} with x_{n_{q}} = x.

The proof that η is onto is similar. Suppose not, and let R ⊂ G be a ray which has no equivalent ray in T. Let T′ be the subtree of T which is the union of all paths in T connecting two vertices of R. By definition of T′, no vertex of T′ can be separated from V (R) in T′ by a connected subgraph of T′. Therefore any ray in T′ would be linked to R by infinitely many disjoint paths in T′, and hence be end-equivalent to R. Since this contradicts our assumptions, T′ must be rayless. Therefore T′ has a vertex x of infinite degree, by König’s Theorem [ 15 ]. By the choice of T′, every edge incident with x can be extended to an x–R path in T′ (Fig. 2).

FIGURE 2.

Pick n ^{∈} ℕ such that x ^{∈} T_{n}, let R′ be the tail of R in R\T_{n}, and let H be the subgraph of T′ spanned by the vertices of R′ together with the x–R′ paths in T′. Note that each vertex of H − x has greater distance from v_{0} in T than x: otherwise consider the smallest k ^{∈} ℕ such that T_{k} ∩ (H − x) contains a vertex v without this property; then d(x_{k}, v_{0}) < d(v, v_{0}) ⩽ d(w, v_{0}) for every w ^{∈} T_{k−1} ∩ H, which contradicts the construction of T since some such w (possibly x) was available for selection as x_{k}. Now pick m > n so that T_{m} ∩ (H − x) ≠ ∅, and a neighbour y of x in H so that xy ^{∈} E(P_{n_{y}}) for some n_{y} > m. Since G [ H − x] is connected, the choice of P_{n_{y}} with x_{n_{y}} = x contradicts the construction of T. □

Using his theory of simplicial decompositions of graphs (see [ 2 ]), Halin [ 9 ] was able to extend Theorem 2.2 to all graphs not containing an infinite subdivided complete graph as a subgraph:

Theorem 2.3. If G is connected and G ⊉ TK_{ℵ_{0}}, then G contains an end-faithful spanning tree.

We shall return to the proof of Theorem 2.3 in Section 4.

3. One-ended graphs

The problem whether or not every connected graph whatsoever contains an end-faithful spanning tree remained open until very recently, and it was generally thought that the answer should be positive. However, Seymour and Thomas [ 18 ], and (a little later but independently) Thomassen [ 20 ] succeeded in constructing graphs which are infinitely connected (and thus have but one end), but whose spanning trees all have infinitely many ends, and are therefore not end-faithful:

Theorem 3.1. There exist one-ended connected graphs which have no end-faithful spanning trees.

By Proposition 2.1, this has the following consequence:

Corollary 3.2. There exist connected graphs which do not contain any end-faithful tree. □

Note, however, that although the graphs obtained from one-ended graphs without end-faithful spanning trees by the construction used in the proof of Proposition 2.1 do not contain end-faithful trees, they do contain end-faithful forests: simply take the (disjoint) union of the additional rays (without their initial vertices) and any one ray from the original graph.

Seymour and Thomas’s counterexample, in its simplest version, can be constructed as follows. Let G_{0} be the graph consisting of ℵ_{1} isolated vertices, put V_{0} := ∅, and let V_{1} be the set of all countable subsets of V (G_{0}). Suppose G_{0}, …, G_{n−1} and V_{0}, …, V_{n} have been defined for some n > 0. To obtain G_{n} from G_{n−1}, add a set V_{S} of ℵ_{1} isolated vertices for each S ^{∈} V_{n}\V_{n−1} (with V_{S} ∩ V_{S′} = ∅ for S ≠ S′), joining every vertex of V_{S} to every vertex in S. To obtain V_{n+1} from V_{n}, add all the countable subsets of the new vertex sets V_{S} (Fig. 3).

FIGURE 3.

The graph G := ⋃_{n^{∈}ℕ} G_{n} (which looks a bit like an inflated version of the 2^{ℵ_{0}}-regular tree), then, is infinitely connected and therefore one-ended. However, Seymour and Thomas prove that any spanning tree of G must contain a subdivision of T_{ℵ_{1}}, the ℵ_{1}-regular tree. Since any such tree has more than one end (in fact, it has at least ℵ_{1}^{ℵ_{0}} = 2^{ℵ_{0}} ends), it cannot be end-faithful in G.

Note that G has 2^{ℵ_{0}} vertices. In the absence of the continuum hypothesis, one may ask whether there might be similar counterexamples of smaller cardinality, say on κ vertices where ℵ_{0} < κ < 2^{ℵ_{0}}. The following result of Komjáth [ 14 ] shows that this is not the case:

Theorem 3.3. If Martin’s axiom holds for κ, then every infinitely connected graph on at most κ vertices has an end-faithful spanning tree.

The existence of end-faithful spanning trees for all graphs of such small cardinalities is thus consistent with the usual axioms of set theory.

The following result of Polat [ 17 ] provides another interesting backdrop for Seymour and Thomas’s example:

Theorem 3.4. Any one-ended connected graph not containing a subdivision of the ℵ_{1}-regular tree has an end-faithful spanning tree.

(Seymour and Thomas [ 18 ] had proved this on the stronger assumption that G is infinitely connected.) The more general problem of whether every TT_{ℵ_{1}}-free connected graph has an end-faithful spanning tree remains open.

In view of the fact that all TK_{ℵ_{0}}-free graphs have end-faithful spanning trees (Theorem 2.3), it is also natural to ask whether or not this is still true for all TK_{ℵ_{1}}-free graphs. Our graph G constructed above contains a TK_{ℵ_{1}}: take the vertices of G_{0} as branch vertices, and join each pair of them to a common ‘upper’ neighbour in G_{1}\G_{0}. (It is easily checked that these neighbours can be chosen distinct for distinct pairs of branch vertices.) However, a slightly more complicated version of this graph, also constructed by Seymour and Thomas [ 18 ], is indeed TK_{ℵ_{1}}-free:

Theorem 3.5. There exists an infinitely connected TK_{ℵ_{1}}-free graph which has no end-faithful spanning tree.

For more results on end-faithful spanning trees in one-ended graphs the reader is referred to Polat [ 17 ]. We conclude this section by mentioning another possible line of research: questions concerning the uniqueness of end-faithful spanning trees. One way to approach this aspect is to ask under what conditions can a given tree or forest in a graph (with η injective) be extended to an end-faithful spanning tree, assuming that some such tree exists.

For example, it is not difficult to see that if G is one-ended, R ⊂ G is a ray, and we know that G contains some end-faithful spanning tree T, then R can be extended to an end-faithful spanning tree of G. The following result is due to Širáň [ 19 ]:

Theorem 3.6. Let G be a countable connected graph. If F ⊂ G is an end-faithful tree or a locally finite end-faithful forest, then F can be extended to an end-faithful spanning tree of G.

(The local finiteness condition here cannot be dropped; see [ 19 ] for an example.)

4. Endings and tree-decompositions

Since all the known connected graphs without end-faithful spanning trees are one-ended, it is natural to ask whether or not these examples are essentially all:

Problem 4.1. If G is connected and such that every one-ended connected induced subgraph has an end-faithful spanning tree, does then G too have an end-faithful spanning tree?

Polat [ 16 ] (combine his Theorem 2.12 and Corollary 2.1) proved this for graphs which contain no system of uncountably many disjoint rays. The technique he uses is the obvious one: to single out, for each end ω of G, a one-ended subgraph G(ω) ⊂ G which somehow ‘contains’ this end, and then to combine end-faithful spanning trees of these subgraphs to an end-faithful spanning tree of G.

On closer inspection, this approach turns out to be harder than it may first appear. To begin with, it is by no means clear how such a subgraph G(ω), called an ending of ω, should be defined. A ‘natural’ translation of an end to a subgraph, taking, say, as G(ω) the subgraph spanned by the union of all the rays in ω, is not of much help: since the rays in ω may have arbitrary initial segments, G(ω) would be no less than the entire graph G! The following recursive definition of an ending G(ω) is more suitable: starting with the union of a maximal set P of disjoint rays from ω, ask at each step in the recursion whether in the subgraph so far constructed there are still rays P, Q ^{∈} P whose tails can be finitely separated; if so, add a path from G to join these tails. When this construction eventually stabilizes, the graph G(ω) obtained will be one-ended, and in the remaining graph G\G(ω) there will be no rays of ω left (by the maximality of P). However, even this definition leaves room for improvement;^{1} the construction of endings actually used by Polat (see [ 17 ]; the definition in [ 16 ] contains an error) is far more complicated still.

The second difficulty which arises with the technique of constructing an end-faithful spanning tree of a graph from end-faithful spanning trees of one-ended subgraphs is that in general the union of infinitely many trees will have more ends than those that live in any one of these trees. Thus, if T_{0}, T_{1}, … are badly chosen end-faithful spanning trees of the endings G(ω_{0}), G(ω_{1}), …, their union T may already contain two disjoint rays from a completely different end ω′ of G, so T could never be extended to a spanning tree of G for which η is 1–1! Similary, T might cover all the vertices of G(ω′) without containing a ray from ω; in this case no extension of T to a spanning tree of G could be such that η is onto. The spanning trees for the individual endings, therefore, have to be chosen with much care if this approach is to work.

Let us look at another way in which the ends of a graph can be tied to its subgraphs. The following theorem from [ 4 ], which characterizes the graphs in which every spanning tree is endfaithful, provides a simple example:

Theorem 4.2. The spanning trees of a connected graph G are all end-faithful if and only if every block of G is rayless.

1 One example: one should include, at the beginning of the construction, the set of neighbours of ω (those vertices of G which cannot be finitely separated from the rays in ω), and then add appropriate finite paths in the recursion to ensure that these neighbours, too, are eventually not finitely separable from the rays in P (just as the other rays in P aren’t).

The non-trivial part of this result is the ‘only if’ direction. For our purposes, however, the ‘if’ part is more interesting: how does the fact that all the spanning trees of the blocks of G are endfaithful—which is trivial if the blocks have no rays—ensure that, when these trees are combined into a spanning tree T of G, this tree will be end-faithful in G? The answer is simple: the ends of G correspond naturally to the ends of its block-cutvertex tree, each of which is in turn traced out by a unique ray of T. (The uniqueness is, of course, up to end-equivalence in T; it holds because any two rays of T following the same end of the block-cutvertex tree of G would share infinitely many of the cutvertices.)

How can we make more general use of this observation? The answer seems to lie in the concept of a tree-decomposition of a graph. Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family F = (B_{λ})_{λ<σ} is called a tree-decomposition of G if the following two conditions hold:

(i) G = ⋃_{λ<σ} B_{λ}; (ii) ∀ μ < σ : ∃ λ < μ : (⋃_{λ<μ} B_{λ}) ∩ B_{μ} ⊂ B_{λ}.

We shall denote the graph ⋃_{λ<μ} B_{λ} in (ii) by G|_{μ}, and its intersection with B_{μ} by S_{μ}.

The reason why such a family F is called a tree-decomposition is that the factors B_{μ} in F may be regarded as the vertices of a tree T_{F} (the decomposition tree of F; Fig. 4), defined inductively by joining each ‘vertex’ B_{μ} to a ‘predecessor’ B_{λ} as provided by (ii) (with λ minimal).^{2}

FIGURE 4.

Now suppose we are interested in the end structure of a graph G given with a tree-decompo-sition F. Suppose further that every S_{μ} is finite. Then, intuitively, any ray in G must either be ‘centred on’ (have infinitely many vertices in) one of the factors B_{λ}, or follow the course of a ray of T_{F}. Moreover, equivalent rays in G must follow the same ray in T_{F} or be centred on the same factor B_{λ}, since their tails would otherwise be separated by one of the (finite) S_{μ}’s. In this way, each end of G either corresponds naturally to an end of T_{F} or lives in a factor of G.

Since the end structure of T_{F} is already simple (as T_{F} is a tree), all that remains to be studied for an understanding of the end structure of G are the ends of the factors B_{μ}. This is precisely how Theorem 2.3 is proved: a TK_{ℵ_{0}}-free graph is shown, essentially, to admit a tree-decomposition into countable connected factors, which have end-faithful spanning trees by Theorem 2.2; these trees are then combined into an end-faithful spanning tree of the whole graph.^{3}

2 For finite σ, this definition becomes equivalent to the definition of a tree-decomposition as introduced by Robertson and Seymour.

Another possible application of this technique would be to try to find a tree-decomposition of G in which all the factors are, essentially,^{4} one-ended. In such a decomposition, the thin ends of G would typically be those that correspond to the ends of T_{F} —note that the rays in these ends would all have to pass through infinitely many (finite) S_{μ}’s—while the thick ends of G would typically (though not necessarily) live in a factor B_{λ}. Let us state this as a problem:

Problem 4.3. Which connected graphs G admit a tree-decomposition F into (essentially) (⩽ one)- ended factors, so that every thick end of G lives in one of these factors and the thin ends of G correspond precisely to the ends of T_{F}?

As a typical example of such a decomposition consider the graph constructed in countably many steps as follows: start with an infinite grid H = ℤ × ℤ; then at each step add countably many disjoint new grids H(v), one for each vertex v added in the previous step, identifying v with one vertex of H(v). The resulting 8-regular graph has a natural tree-decomposition into ℤ × ℤ grids, in which every S_{μ} consists of a single vertex. Its thick ends are precisely these grids, while its thin ends correspond to the ends of its decomposition tree.

The reader familiar with the interplay between graphs and groups will have recognized the above example as a Cayley graph of the group ℤ^{2} ∗ ℤ^{2}, where ℤ^{2} is the free abelian group on two generators, and ℤ^{2} ∗ ℤ^{2} is the free product of ℤ^{2} with itself. This is not a coincidence: Cayley graphs of finitely generated groups are prime examples of graphs with such a tree structure. As Thomassen and Woess [ 21 ] have recently shown, all Cayley graphs of accessible groups have a tree structure as described in (4.3). (‘Most’ finitely generated groups, including all finitely presented ones, are accessible; in fact, a well-known conjecture of Wall, which said that all finitely generated groups were accessible, was only very recently disproved by Dunwoody [ 6 ].)

In fact, Thomassen and Woess [ 21 ] show more than this: they prove that a locally finite connected vertex-transitive graph G has a tree structure as in (4.3) whenever there exists a natural number k such that any two ends of G can be separated by at most k vertices. (For Cayley graphs, this latter condition is shown to be equivalent to the accessibility of the corresponding group.) Their proof uses Dunwoody structure trees, a concept similar to tree-decompositions, and their paper contains a very commendable self-contained introduction to this technique.

3 It would be misleading to give the impression that this is completely straightforward; see [ 3 ] for a detailed account of how the technique is implemented.

4 It may be more realistic to consider the factors B_{λ} not as they are, but equipped with a few additional edges.

These edges would typically join vertices of B_{λ} which can be linked in G by a path whose interior lies outside B_{λ}, thus allowing us to consider (for the end structure of B_{λ}) any rays in G which are centred on but have no tail in B_{λ}.

5. Topological aspects

In this last section we take a look at the end structure of a graph from a (point set) topological angle. Its end set Ω is given a natural topology, which bears out the intuitive notion that an end should represent something like a ‘point at infinity’ for equivalent rays. This topology, moreover, offers an additional level at which we can pursue our original idea, the aim of representing the end structure of a given graph faithfully by a simple subgraph: we can now ask that a spanning forest (say) should not only represent the ends of its underlying graph completely and uniquely (i.e. with η a bijection), but that the topology of the original end space should be reflected too.

If a finite set S ⊂ V (G) does not separate two ends ω and ω′ in G, let us write ω ∼_{S} ω′. Similarly, for x ^{∈} V (G) and ω ^{∈} Ω(G) we write x ∼_{S} ω if x is in the component of G − S which contains a tail of every ray from ω. For x, y ^{∈} V (G), finally, we write x ∼_{S} y if either x = y ^{∈} S or x and y are in the same component of G − S.

Now let Ω(G) be endowed with the topology whose basic open sets are the sets of the form { ω′ | ω′ ∼_{S} ω }, where S is a finite subset of V (G) and ω ^{∈} Ω(G). It is easy to check that the intersection of two such sets is again a union of other such sets, so these sets do indeed form a basis of a topology on Ω(G).

Problem 5.1. Which topological spaces can be represented as Ω(G) for some graph G?

A topological space of the from Ω(G) is not in general metrizable (see below). However, it is always induced by a uniformity. Indeed, the sets { y | y ∼_{S} x }, where now x, y ^{∈} V (G) ∪ Ω(G) and S varies over the finite subsets of V (G), form a basis of vicinities for a uniform space, whose induced topology on Ω(G) coincides with the topology we defined above. Moreover, this space is a natural completion of its (discrete) restriction to V (G).

Clearly, the uniform space on Ω(G) is totally bounded if and only if for every finite S ⊂ V (G) there are at most finitely many ends which are pairwise separated by S (i.e. G − S has only finitely many components containing rays). Since Ω(G) is Hausdorff and complete (being a closed subspace of V (G) ∪ Ω(G), which is complete), this is then equivalent to Ω(G) being compact. See Polat [ 16 ] for (a lot) more details.

Returning to our theme of end-faithfulness, let us call H ⊂ G topologically end-faithful if the map η defined in § 1 is not only a bijection but even a homeomorphism between Ω(H) and Ω(G). The following observation is immediate from the definition of η:

Proposition 5.2. For every H ⊂ G, η is (uniformly) continuous. □

Thus, if η is a bijection and Ω(H) happens to be compact, then η is indeed a homeomorphism:

Corollary 5.3. If H ⊂ G is end-faithful, and such that for every finite S ⊂ V (H) at most finitely many of the components of H − S contain a ray, then H is topologically end-faithful in G. □

On the other hand, it is not difficult to find graphs whose end space is compact but which cannot contain an end-faithful forest whose end space is also compact. For example, let the graph K be obtained from an uncountable complete graph K′ by attaching a ray to each of its vertices (as in the proof of Proposition 2.1). Ω(K) is clearly compact: deleting finitely many vertices from K never leaves more than finitely many components. (It is also easy to verify the compactness of K directly: since any basic open set O which contains the end κ corresponding to K′ will also contain all but finitely many of the other ends, { O } is easily extended to a finite open cover of Ω(K).) However, there cannot be an end-faithful forest F ⊂ K whose end space is compact: since F would have to contain uncountably many disjoint rays, there would either be a vertex of infinite degree (whose deletion separates infinitely many ends), or F would already have infinitely many rays in pairwise distinct components. Thus, a set S ⊂ V (F) with at most one vertex would ‘partition’ Ω(F) into infinitely many open sets of the form { ω′ | ω′ ∼_{S} ω }.

The topological version of our first and main question, Problem 1.1, is therefore just as interesting as the original:

Problem 5.4. Which graphs contain a topologically end-faithful forest?

Problem 5.4 seems interesting both from a graph theoretical and from a topological point of view. For example, is the graph K in any way prototypical for the graphs not containing a topologically end-faithful forest? Can the graphs that do contain a topologically end-faithful forest be characterized by excluding K in some sense? Does G contain a topologically end-faithful forest if Ω(G) is metrizable? (Ω(K) is clearly not metrizable: since any open ball of radius 1/n around κ would only be allowed to exclude finitely many points, the intersection of these balls over all n ^{∈} ℕ could only exclude countably many points, leaving κ at distance zero from uncountably many points of Ω(K). On the other hand, it is not difficult to see that Ω(T) arises from a metric, even an ultrametric, if T is a tree.)

We conclude with an observation that implies a first positive result concerning Problem 5.4. Call a rooted spanning tree T of G normal if the endvertices of every edge of G are comparable

in the tree order <_{T} which T induces on V (G). Thus, if r is the root of T and xy ^{∈} E(G), then x lies on the r–y path in T or y lies on the r–x path in T. (Intuitively, all the edges of G are ‘along’ branches of T, never ‘across’.) We shall denote the vertex set of the r–x path in T by ⌊x⌋; then ⌊x⌋ = { v | v ⩽_{T} x }. If x <_{T} y, we say that y lies above x in T (etc.).

Jung [ 13 ] showed that every countable connected graph has a normal spanning tree, and Halin [ 9 ] proved that every connected graph without a TK_{ℵ_{0}} subgraph contains such a tree. (This is in fact the original version of our Theorem 2.3, which then follows easily by Proposition 5.5 below.) For a full characterization of the graphs containing normal spanning trees see Jung’s paper [ 13 ], or Halin [ 10 ].

Proposition 5.5. Normal spanning trees are topologically end-faithful.

Proof. Let T be a normal spanning tree of a graph G, say with root r, and let η be the canonical map Ω(T) → Ω(G). It is not difficult to show (see [ 5 ]) that

if x, y ^{∈} V (G) are incomparable in <_{T}, and if z = inf { x, y }, then ⌊z⌋ separates x from y in G. (∗)

(∗) immediately implies that η is 1–1. Indeed, if ω and ω′ are distinct ends of T, and if R ^{∈} ω and R′ ^{∈} ω′ are chosen so as to start in r, then R and R′ coincide up to some last vertex z, and ⌊z⌋ separates the tails zR and zR′ in G. Hence R and R′ are also non-equivalent in G.

Let us now use (∗) to prove that η is onto. Let ω ^{∈} Ω(G) be given, and pick a ray R ^{∈} ω that starts in r. We show that T contains a ray x_{0}x_{1} … which R meets infinitely often. Let x_{0} := r. Suppose vertices x_{0}, …, x_{n} have been chosen so that they induce an increasing path in T and infinitely many vertices of R lie above x_{n}. By (∗), x_{n} has a unique upper neighbour y in T such that R has infinitely many vertices above y (because R can pass through ⌊x_{n}⌋ only finitely often); put x_{n+1} := y.

In order to show that R meets x_{0}x_{1} … infinitely often, suppose x_{n} is the last vertex of R that belongs to { x_{0}, x_{1}, … } (recall that x_{0} = r ^{∈} R by assumption). Let y be the next vertex on R, and let m be the r–y distance in T. Then y and x_{m} have the same distance from r in T, and y ≠ x_{m}; so y and x_{m} must be incomparable. By definition of x_{m}, the tail yR of R starting in y has a vertex x above x_{m}. Then y is incomparable with x, and inf { x, y } <_{T} x_{m}. By (∗), this implies that yR meets ⌊x_{m}⌋ = { x_{0}, …, x_{m} }, contrary to the choice of x_{n}.

We complete the proof by showing that η^{−1} is uniformly continuous (cf. Proposition 5.2). We thus have to show that for every finite S ⊂ V (T) there exists a finite S′ ⊂ V (G) such that η(ω) ∼_{S′} η(ω′) implies ω ∼_{S} ω′. Given S, let us set S′ := ⌊S⌋ := ⋃{ ⌊s⌋ | s ^{∈} S }. Now let ω, ω′ ^{∈} Ω(T) be such that η(ω) ∼_{S′} η(ω′). In order to show ω ∼_{S} ω′, let R ^{∈} ω and R′ ^{∈} ω′ be given; we may assume that both rays start at r. Let u be the last common vertex of R and R′. By (∗), ⌊u⌋ separates (the tails of) R and R′ in G. Therefore ⌊u⌋ ⊄ S′, so no vertex v ⩾_{T} u can be in S. In particular, S does not separate (the tails of) R and R′ in T, so ω ∼_{S} ω′ as required. □

Corollary 5.6. If G is countable or if G ⊉ TK_{ℵ_{0}}, then G contains a topologically end-faithful forest.

Proof. By Jung’s result or by Halin’s theorem (the normal tree version of Theorem 2.3), each component of G contains a normal spanning tree. By Proposition 5.5, their union is topologically end-faithful in G. □

References

[1] W. Dicks and M. J. Dunwoody, Groups Acting on Graphs, Cambridge University Press, Cambridge 1989.

[2] R. Diestel, Graph Decompositions—a study in infinite graph theory, Oxford University Press, Oxford 1990.

[3] R. Diestel, On end-faithful spanning trees in infinite graphs, Math. Proc. Camb. Phil. Soc. 107 (1990), 461–473.

[4] R. Diestel, On spanning trees and k-connectedness in infinite graphs, submitted.

[5] R. Diestel and I. Leader, A proof of the Bounded Graph Conjecture, submitted.

[6] M. J. Dunwoody, An inaccessible finitely generated group, preprint 1991

[7] H. Freudenthal, Über die Enden diskreter Räume und Gruppen, Comm. Math. Helv. 17 (1944), 1–38.

[8] R. Halin, Über unendliche Wege in Graphen, Math. Ann. 157 (1964), 125–137.

[9] R. Halin, Simplicial decompositions of infinite graphs, in: (B. Bollobás, Ed.) Advances in Graph Theory (Annals of Discrete Mathematics 3), North-Holland Publ. Co., Amsterdam/London 1978.

[10] R. Halin, Graphentheorie II, Wissenschaftliche Buchgesellschaft, Darmstadt 1981.

[11] H. Hopf, Enden offener Räume und unendliche diskontinuierliche Gruppen, Comm. Math. Helv. 15 (1943), 27–32.

[12] W. Imrich and N. Seifter, A survey on graphs with polynomial growth, in (R. Diestel, Ed.): Directions in Infinite Graph Theory and Combinatorics, Annals of Discrete Mathematics, to appear.

[13] H. A. Jung, Wurzelbäume und unendliche Wege in Graphen, Math. Nachr. 41 (1969), 1–22.

[14] P. Komjáth, Martin’s axiom and spanning trees of infinite graphs, preprint 1990.

[15] D. König, Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig 1936 (reprinted: Chelsea, New York 1950).

[16] N. Polat, Topological aspects of infinite graphs, in: (G. Hahn et al., Eds.) Cycles and Rays, NATO ASI Ser. C, Kluwer Academic Publishers, Dordrecht 1990.

[17] N. Polat, Spanning trees of infinite graphs, preprint 1989.

[18] P. D. Seymour and R. Thomas, An end-faithful spanning tree counterexample, in (R. Diestel, Ed.): Directions in Infinite Graph Theory and Combinatorics, Annals of Discrete Mathematics, to appear.

[19] J. Širáň, End-faithful forests and spanning trees in infinite graphs, in (R. Diestel, Ed.): Directions in Infinite Graph Theory and Combinatorics, Annals of Discrete Mathematics, to appear.

[20] C. Thomassen, Infinite connected graphs with no end-preserving spanning trees, preprint 1990.

[21] C. Thomassen and W. Woess, Vertex-transitive graphs and accessibility, preprint 1991.

Reinhard Diestel, Faculty of Mathematics (SFB 343), Bielefeld University, P.O. Box 8640 D-4800 Bielefeld, Germany