On Spanning Trees and k-connectedness in Infinite Graphs

Reinhard Diestel

We prove a conjecture of Širáň describing the graphs in which every spanning tree is end-faithful. This result leads to the consideration of infinite k-connected rayless graphs. We characterize these graphs in terms of tree-decompositions into finite k-connected factors.

Introduction

Let G be an infinite graph. The following assertions are equivalent for rays (1-way infinite paths) P, Q ⊂ G:

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

(ii) for every finite X ⊂ G, the infinite components of P \X and Q\X lie in the same component of G\X;

(iii) G contains infinitely many disjoint (possibly trivial) P –Q paths.

If two rays P, Q ⊂ G satisfy (i)–(iii), we call them end-equivalent in G. An end of G is an equivalence class under this relation, and E(G) denotes the set of ends of G. For example, the 2-way infinite ladder has two ends, the infinite grid ℤ × ℤ and every infinite complete graph have one end, and the dyadic tree has 2^{ℵ_{0}} ends.

This paper is concerned with the relationship between the ends of a connected graph G and the ends of its spanning trees. If T is a spanning tree of G and P, Q are end-equivalent rays in T, then clearly P and Q are also endequivalent in G. We therefore have a natural map η : E(T) → E(G) mapping each end of T to the end of G containing it. In general, η need be neither 1–1 nor onto. For example, the 2-way infinite ladder has a spanning tree with 4 ends (the tree consisting of its two sides together with one rung), and every infinite complete graph is spanned by a star, which has no ends at all. A spanning tree T of G for which η is 1–1 and onto is called end-faithful.

The concept of ends in graphs, and of end-faithful spanning trees, was introduced by Halin [ 4 ] in 1964. Halin asked whether every infinite connected graph has an end-faithful spanning tree, and proved that this is so for all countable graphs. End-faithful spanning trees have since been constructed for some classes of uncountable graphs as well (see [ 2 ] and, especially, Polat [ 8 ]), but very recent results due to Seymour and Thomas [ 10 ] and to Thomassen [ 12 ] show that some uncountable graphs have no such tree. See [ 3 ] for an up-to-date survey of results and open problems in this field.

The purpose of this paper is to solve the problem converse to Halin’s, which was posed recently by Širáň [ 11 ]: is there a simple characterization of the graphs in which every spanning tree is end-faithful? Širáň conjectured the following, which will be the first main result of this paper:

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

The first part of this paper is devoted to a proof of this theorem, embedded in a slightly more general result (Theorem 2.1).

The fact that Širáň’s conjecture is true immediately raises a further question: what do the 2-connected rayless graphs look like? (Interestingly, the graphs in which every block is rayless appear in a similar but unrelated role in a recent paper of Halin [ 6 ], which motivates this question further.) Moreover, if we replace 2 with a more general natural k, we obtain a problem of quite independent interest: is there a simple structural description of the k-connected rayless graphs?

Note that this problem too is intrinsically infinite: the raylessness condition does not bite in the finite case, and the finite k-connected graphs are clearly too varied to permit a general structural description of any detail.

In the second part of the paper, then, we shall prove what is best possible in such a case: that the uncontrollable element in the variation among the kconnected rayless graphs is confined to the finite case. More precisely, we show that an infinite graph is rayless and k-connected if and only if the ‘infinite aspect’ of its structure is that of an arbitrary rayless tree, while the ‘finite details’ of this tree are arbitrary finite k-connected graphs:

Theorem B. An infinite graph is rayless and k-connected if and only if it has a k-connected rayless tree-decomposition into finite k-connected factors.

(See Section 3 for precise definitions.)

Corollary. Every finite subgraph of a rayless k-connected graph can be extended to a k-connected finite subgraph.

In particular, we see that every rayless k-connected graph must have a finite k-connected subgraph.

1. Terminology and basic lemmas

We now run through some of the terminology and basic facts needed later. A subgraph H of G is attached to a connected subgraph H′ of G\H if every vertex of H is adjacent to a vertex in H′. If H is attached to some component of G\H, then H is attached in G; otherwise H is unattached. (Note that if G ≠ ∅, then the empty graph ∅ ⊂ G is attached in G.)

If P = x_{1} … x_{n} is a path and 1 ⩽ i ⩽ j ⩽ n, we write P̊ := x_{2} … x_{n−1}, P x_{i} := x_{1} … x_{i}, P x̊_{i} := x_{1} … x_{i−1}, x_{i}P x_{j} := x_{i} … x_{j}, x_{j}P := x_{j} … x_{n} and x̊_{j}P := x_{j+1} … x_{n} for subpaths of P. Analogous notation will be used for rays.

For X, Y ⊂ G, we call a path P ⊂ G an X–Y path if its endvertices are in X and Y, respectively, and its interior P̊ lies in G∖(X ∪Y). We write G [ X → Y ] for the subgraph of G induced by all vertices of G that can be reached from X without passing through Y. More precisely, G [ X → Y ] is the subgraph of G induced by all vertices v ^{∈} G for which G contains a path x_{1} … x_{n} satisfying x_{1} ^{∈} X, x_{n} = v, and x_{i} /^{∈} Y for i ≠ n. When the underlying graph G is fixed, we shall usually abbreviate G [ X → Y ] ∩ Y to Y [ X]. Thus, if X and Y are disjoint, then Y [ X] is the subgraph of Y induced by all terminal vertices of X–Y paths in G. On the other hand, if Y = G, then our definition of Y [ X] coincides with the conventional meaning of G [ X], denoting the subgraph of G induced by the vertices of X. A frequent example for the use of this notation is the following. If H is an induced subgraph of G and C is a component of G\H, then H [ C] is spanned by all those vertices of H that have a neighbour in C. Then H = H [ C] if and only if H is attached to C in G.

For X ⊂ G and v ^{∈} G, any union F of paths P_{i} (i ^{∈} I) which begin in v, end in some vertex of X, and are disjoint except for v, will be called a v–X fan, with branches v̊P_{i}. Note that neither v nor the branches of F are required to lie outside X. If R ⊂ G is a ray and G contains an infinite v–R fan, then v is called a neighbour of R in G. Note that if v is a neighbour of R, then G also contains an infinite v–R fan which covers V (R): simply take any v–R fan, prune each branch after its first vertex on R, and extend the shortened branches along R to cover all its vertices. (If v ^{∈} R, one may have to add an extra branch.)

Similarly for X, Y ⊂ G, any union of disjoint paths, each beginning in X and ending in Y, will be called an X–Y linkage. Thus two rays in G are endequivalent if and only if G contains an infinite linkage between them.

Two or more paths are independent if their interiors are disjoint. The Menger number μ_{G}(x, y) of two vertices x, y ^{∈} G is the maximum of all cardinals κ for which there exists a κ-set of independent x–y paths in G. (It is not difficult to prove that this maximum always exists.) By Menger’s theorem, the number of vertices needed to separate nonadjacent vertices x, y in G is exactly μ_{G}(x, y), and G is called κ-connected if μ_{G}(x, y) ⩾ κ for all x, y ^{∈} G. We shall use the infinite version of Menger’s theorem (for finite κ) freely throughout the paper; see e.g. Halin [ 5 ] for a simple proof.

Another standard result we shall be using repeatedly is König’s Infinity Lemma [ 7 ]:

Infinity Lemma. Let K be a graph whose vertex set is the disjoint union of finite non-empty sets A_{n}, n ^{∈} ℕ, such that for n > 0 every vertex in A_{n} has a neighbour in A_{n−1}. Then K contains a ray x_{0}x_{1} … with x_{n} ^{∈} A_{n} for all n ^{∈} ℕ.

Corollary 1.1. Every infinite connected locally finite graph has a ray. □

Lemma 1.2. Let U and C be disjoint subgraphs of a graph G, such that C is connected, U is attached to C, and U is infinite. Then G contains either an infinite v–U fan for some v ^{∈} C, or an infinite R–U linkage for some ray R ⊂ C.

Proof. We first construct a ‘minimal’ connected subgraph T of G [ C → U ] containing infinitely many vertices of U. Pick an ω-sequence u_{0}, u_{1}, … ^{∈} V (U). Let u′_{0} be a neighbour of u_{0} in C, and set T_{0} := u_{0}u′_{0}. Having constructed T_{0}, …, T_{n} for some n ^{∈} ℕ, let P be a U – (T_{n} ∩ C) path beginning in u_{n+1}, and set T_{n+1} := T_{n} ∪ P. Finally, set T := ⋃_{n^{∈}ℕ} T_{n}.

By construction, T is a tree with leaves u_{0}, u_{1}, …, and every vertex of T lies on a U–U path in T. Thus, if T has a vertex v of infinite degree, then v ^{∈} C, and T contains an infinite v–U fan.

Suppose now that T is locally finite, and let R ⊂ T be a ray (by Corollary 1.1). Choose an ω-sequence P_{0}, P_{1}, … of disjoint R–U paths in T, as follows. Let P_{0} be any R–U path in T. Assume that P_{0}, …, P_{n} have been chosen for some n ^{∈} ℕ. Choose x ^{∈} R such that Q_{n} := Rx ∪ P_{0} ∪ … ∪ P_{n} is connected, and let C_{n} denote the component of T − x containing x̊R. Since Q_{n} is a subtree of T disjoint from C_{n}, and since every vertex of C_{n} lies on a U–U path in T, we may choose P_{n+1} as an R–U path in C_{n}. The paths P_{0}, P_{1}, … form an infinite R–U linkage, as desired. □

2. The graphs in which every spanning tree is end-faithful

As our first main result, let us now prove Širáň’s conjecture (Theorem A), embedded in a slightly more comprehensive characterization of the graphs in which every spanning tree is end-faithful.

Theorem 2.1. For every connected graph G, the following assertions are equivalent:

(a) every spanning tree of G is end-faithful;

(b) every block of G is such that all its spanning trees are end-faithful;

(c) every block of G is rayless;

(d) G has no two disjoint equivalent rays, and no ray of G has a neighbour.

Proof. (a)→(d). Suppose that every spanning tree of G is end-faithful. Then G has clearly no two disjoint equivalent rays; for the union of these rays could be extended to a spanning tree of G, which would not be end-faithful. Now suppose that R is a ray in G with a neighbour v. Choose a v–R fan F ⊂ G that covers V (R), and extend F to a spanning tree T of G. We prove that T has no ray equivalent to R, and is therefore not end-faithful. Let Q be any ray in G equivalent to R. Then Q meets R infinitely often (because G has no two disjoint equivalent rays), and hence Q meets more than two branches of F. Thus Q ∪ F contains a cycle. As T = T ∪ F is acyclic, this implies that Q ⊄ T.

(d)→(c). Let B be a block of G. We assume that B contains a ray R, and show that unless R has a neighbour, B contains two disjoint rays equivalent to R. We shall consider the vertices of R as ordered in the natural way, with x < y if x is nearer to the initial vertex of R than y.

Let C be the set of components of B\R. If R [ C] is infinite for some C ^{∈} C, the assertion follows by Lemma 1.2: unless C contains a neighbour of R, there exists a ray in C (and hence disjoint from R) which is equivalent to R. We shall therefore assume that R [ C] is finite for every C ^{∈} C. Regarding C_{1}, C_{2} ^{∈} C as equivalent if R [ C_{1} ] = R [ C_{2} ], let C′ ⊂ C be a set of representatives, and put B′ := B [ R ∪ ⋃ C′]. Note that B′ is still 2-connected. We may assume that

each vertex x ^{∈} R is adjacent to only finitely many vertices of R, and x is contained in R [ C] for only finitely many C ^{∈} C′. (1)

For if x is adjacent to infinitely many vertices of R, then x is a neighbour of R. Similarly if C′′ ⊂ C′ is infinite, then infinitely many vertices of R are in R [ C] for some C ^{∈} C′′, by the choice of C′. Thus if x ^{∈} R [ C] for every C ^{∈} C′′, then B′ contains an infinite x–R fan, so again x is a neighbour of R.

(1) implies that, from any given vertex of R, we can only reach finitely many other vertices of R by an R–R path in B′. More generally,

V_{x} := { v ^{∈} R | B′ contains an R–R path u … v with u < x } is finite for every x ^{∈} R̊.

(2)

Note that since x is not a cutvertex of B′, V_{x} contains a vertex y > x. In particular, max V_{x} > x.

Choose a sequence P_{1}, P_{2}, … of paths as follows. Let y_{0} be the second vertex on R. Having defined y_{n} for some n ^{∈} ℕ, put y_{n+1} := max V_{y_{n}}, let P_{n+1} be an Rẙ_{n}–R path ending in y_{n+1}, and let x_{n+1} be the initial vertex of P_{n+1}. Note that

x_{n+1} < y_{n} < y_{n+1}  for all n ^{∈} ℕ.  (3)

Moreover, we have

y_{n} ⩽ x_{n+2}  for all n  (4)

FIGURE 1. Finding two disjoint rays equivalent to R

(Fig. 1). For if x_{n+2} < y_{n}, then P_{n+2} is an Rẙ_{n}–R path, so its endvertex y_{n+2} is in V_{y_{n}}. Since y_{n+2} > y_{n+1} by (3), this contradicts the choice of y_{n+1} as max V_{y_{n}}.

Combining (3) and (4), one easily deduces that none of the R-segments y_{n}Rx_{n+2} contains any other vertices x_{i} or y_{i}. In particular, two such segments are disjoint for distinct n. Furthermore, if n ≠ m and P̊_{n}, P̊_{m} ≠ ∅, then P̊_{n} and P̊_{m} lie in different components C ^{∈} C′, by the choice of their endvertices y_{n} and y_{m}, and the fact that these are distinct. Hence, the rays

x_{1}P_{1}y_{1}Rx_{3}P_{3}y_{3}Rx_{5}P_{5}y_{5} … and x_{2}P_{2}y_{2}Rx_{4}P_{4}y_{4}Rx_{6}P_{6}y_{6} …

are disjoint. Since both meet R infinitely often, they are also equivalent.

(c)→(b) is trivial, because a rayless graph has no ends.

(b)→(a). Suppose that G has a spanning tree T which is not end-faithful. Assume first that two ends of T are contained in a common end of G. Then T has two disjoint rays R and Q, such that G contains an infinite R–Q linkage L. By discarding initial segments of R and Q if necessary, we may assume that H := R ∪ Q ∪ L is 2-connected. Thus H ⊂ B for a block B of G, and B ∩ T is a spanning tree of B which is not end-faithful.

Assume now that G contains a ray R which has no equivalent ray in T. For each edge e of R, let B(e) be the block of G containing e. Note that if B(e_{1}) = B(e_{2}), then B(e_{1}) = B(e) = B(e_{2}) for every edge e between e_{1} and e_{2} on R. We show that B := { B(e) | e ^{∈} E(R) } is finite; then R has a tail xR inside a single block B, and B ∩ T is a spanning tree of B which is not end-faithful.

Suppose B is infinite, and assume that E(R) runs through the blocks B_{0}, B_{1}, … (in the order of R). For each n ^{∈} ℕ, let x_{n} be the first vertex on R that is in B_{n}. Then B(e) = B_{n} for every edge e between x_{n} and x_{n+1}, so x_{n}, x_{n+1} ^{∈} B_{n}. Since T ∩ B_{n} is connected, it contains an x_{n}–x_{n+1} path P_{n}. These paths are independent for distinct n, so x_{1}P_{1}x_{2}P_{2}x_{3}P_{3} … is a ray in T which meets R infinitely often. This contradicts our assumption that T has no ray equivalent to R. □

In proving Širáň’s conjecture, we have described the graphs in which every spanning tree is end-faithful in terms of rayless 2-connected graphs. In the remainder of this paper, we take this description a step further and characterize the rayless 2-connected graphs in terms of finite ones. The two results can then be combined into a structural characterization of the graphs in which every spanning tree is end-faithful in terms of finite 2-connected graphs. (The explicit formulation of this result should be clear and will be left to the reader.)

3. Tree-decompositions and convex subgraphs

The aim of this section is to provide the necessary background for the proof of our second main result, a characterization of the infinite rayless k-connected graphs by their tree-decompositions (Theorem 4.3). The factors in these treedecompositions will be finite k-connected graphs, and the decomposition trees involved will be rayless and such that ‘adjacent’ factors overlap in at least k vertices. Although this result is easily stated (at least in an intuitive way), its proof uses a few concepts and techniques from simplicial decomposition theory as developed in [ 1 ]. In order to make this paper self-contained, everything needed is listed below; the reader who is familiar with simplicial decompositions may skip this material and go straight to Section 4.

In the following, a complete graph will often be called a simplex. Let G be a graph, σ > 0 an ordinal, and for each λ < σ let B_{λ} be an induced subgraph of G. The family F = (B_{λ})_{λ<σ} is called a simplicial tree-decomposition of G if the following four conditions hold: (S1) G = ⋃_{λ<σ} B_{λ}; (S2) every G|_{μ} ∩ B_{μ} =: S_{μ} is a simplex, where G|_{μ} := ⋃_{λ<μ} B_{λ} (0 < μ < σ); (S3) no S_{μ} contains B_{μ} or any other B_{λ} (0 ⩽ λ < μ < σ); (S4) each S_{μ} is contained in B_{λ} for some λ < μ (μ < σ). Based on (S1), we shall write λ(x) := min { λ | x ^{∈} B_{λ} } for vertices x ^{∈} G, and Λ(X) := { λ(x) | x ^{∈} X } for X ⊂ G. Note that the vertices x ^{∈} G with λ(x) = μ are precisely the vertices of B_{μ}\S_{μ}.

If F satisfies (S1) and (S4) (but not necessarily (S2) or (S3)), F is called a tree-decomposition of G. The factors in such a tree-decomposition may be regarded as the vertices of a tree T_{F} (the decomposition tree of F), defined inductively by joining each ‘vertex’ B_{μ} to a fixed predecessor B_{λ} as provided by (S4). To avoid ambiguity, this λ is chosen minimal; then S_{μ} is contained in B_{λ} but not in S_{λ}, so S_{μ} has a vertex s with λ(s) = λ. It is often convenient to think of the tree T_{F} as rooted at the vertex B_{0}, and of V (T_{F}) = { B_{λ} | λ < σ } as endowed with the corresponding tree-order <_{T_{F}}. (Thus, B <_{T_{F}} B′ if B lies on the unique B_{0}–B′ path in T_{F}.) Note that this partial order is compatible with the well-ordering of F: if B_{λ} <_{T_{F}} B_{μ}, then λ < μ.

We remark that the above definition of a tree-decomposition is equivalent, for finite graphs, to that introduced by Robertson and Seymour for the study of graph minors; see [ 1; Ch. 1, Exercise 23 ].

We shall need the following simple property of tree-decompositions (see [ 1; Ch. 1.2 ] for a proof):

Proposition 3.1. If B, B′, B′′ are factors in a tree-decomposition F of G and B lies on the B′–B′′ path in T_{F}, then B separates B′\B from B′′\B in G.

A tree-decomposition or simplicial tree-decomposition F = (B_{λ})_{λ<σ} is coherent if S_{μ} is attached to B_{μ}\S_{μ} and B_{μ}\S_{μ} is connected for every μ < σ. F will be called k-connected if |S_{μ}| ⩾ k for every μ > 0, and rayless if T_{F} is rayless. For each B ^{∈} F, the subgraph

B^{−} := ⋃ { B′ ^{∈} F | B′ ⩽_{T_{F}} B }

of G will be called the shadow of B in T_{F}. Since B_{λ(s)} <_{T_{F}} B_{μ} for all s ^{∈} S_{μ} (induction on μ), we have B^{−} = ⋃ { B_{λ(x)} | x ^{∈} B^{−} } for every B ^{∈} F.

A subgraph H ⊂ G is convex in G if H contains every induced path in G whose endvertices are in H. Examples of convex subgraphs include factors and shadows in simplicial tree-decompositions [ 1; Ch. 5.4 ]:

Proposition 3.2. If F = (B_{λ})_{λ<σ} is a simplicial tree-decomposition of G and T is a subtree of T_{F}, then ⋃ T is a convex subgraph of G.

There are a number of interesting and useful equivalents of convexity, all easily proved:

Proposition 3.3. For H ⊂ G, the following statements are equivalent: (i) H is convex in G; (ii) the endvertices of every H–H path in G are adjacent in H; (iii) H is an induced subgraph of G and, for every vertex x ^{∈} G\H, the

subgraph H [ x] = G [ x → H] ∩ H is a simplex; (iv) if A, B, X ⊂ V (H), then X separates A from B in H if and only if X

separates A from B in G. □

The following simple technical lemma provides a useful means for joining two convex subgraphs into one.

Lemma 3.4. Let G_{1}, G_{2} ⊂ G be graphs, and suppose that S = G_{1} ∩ G_{2} separates G_{1} from G_{2} in G.

(i) If G_{1} and G_{2} are convex in G, then so is G_{1} ∪ G_{2}.

(ii) If S is a simplex and G_{i} is convex in G [ G_{i} → S], i = 1, 2, then G_{1} ∪ G_{2} is convex in G.

Proof. (i) is obvious from the definition of convexity.

(ii) As S is a simplex, G [ G_{i} → S] is convex in G by Proposition 3.3. Since G_{i} is convex in G [ G_{i} → S] by assumption, this implies that G_{i} is also convex in G. Apply (i). □

4. The structure of the rayless k-connected graphs

Given a graph G and a cardinal κ, let [ G]_{κ} denote the graph with vertex set V (G) and edge set E(G) ∪ { xy | μ_{G}(x, y) ⩾ κ }. The graph [ G]_{κ} is usually called the κ-closure of G, which is justified by the following observation:

Proposition 4.1. [ G]_{κ} is its own κ-closure.

(The proof of Proposition 4.1 is not difficult; see [ 1; Ch. 5.3 ].)

Note that Proposition 4.1 implies that μ_{[ G]_{κ}}(x, y) < κ for any two nonadjacent vertices x, y ^{∈} [ G]_{κ}. Moreover,

Lemma 4.2. If κ is infinite and G is rayless, then [ G]_{κ} is rayless.

Proof. Suppose [ G]_{κ} contains a ray R. We shall choose vertices x_{n} ^{∈} R and define paths P_{n} ⊂ G, for all n ^{∈} ℕ, such that P_{n} is an x_{n−1}–x_{n} path for each n ⩾ 1, and ⋃_{n^{∈}ℕ} P_{n} is a ray in G.

Let x_{0} be the initial vertex of R and P_{0} := { x_{0} }. Let n ⩾ 1 be given, and assume that x_{i} and P_{i} have been defined for all i < n. Let v be the successor of x_{n−1} on R. If x_{n−1}v ^{∈} E(G), let P_{n} := x_{n−1}v and set x_{n} := v. If x_{n−1}v /^{∈} E(G), then G contains infinitely many independent x_{n−1}–v paths. Let P be one of these paths, chosen such that P̊∩ P_{i} = ∅ for all i < n. Let x_{n} be the latest (farthest from x_{0}) vertex on R that is in V (P), and set P_{n} := P x_{n}.

It is easily checked that ⋃_{n^{∈}ℕ} P_{n} is a ray in G. □

We are now ready to prove our second main result.

Theorem 4.3. For any graph G and k ^{∈} ℕ, the following two assertions are equivalent:

(i) G is rayless and k-connected; (ii) G has a rayless and k-connected tree-decomposition into finite k-

connected factors.

Proof. (i)→(ii). Assume that G is rayless and k-connected, and let G′ := [ G]_{ℵ_{0}}. Clearly G′ is again k-connected, and by Lemma 4.2, G′ is also rayless. We shall first construct a rayless, k-connected and coherent simplicial tree-decomposition F′ = (B_{λ})_{λ<σ} of G′, which will then be modified to give the desired tree-decomposition F of G.

Let us choose the factors B_{λ} for F′ in such a way that, for every λ < σ,

(a) B_{λ} is unattached in G′;

(b) if xy ^{∈} E(B_{λ})\E(G) and λ(y) = λ, then B_{λ} ∩ G contains at least k independent x–y paths;

(c) ⋃_{λ′⩽λ} B_{λ′} is convex in G′.

Let μ ⩾ 0 be given, and suppose that for every λ < μ we have defined B_{λ} so as to satisfy (a)–(c). We shall seek to define B_{μ} in such a way that (a)–(c) hold for λ = μ.

We first show that G′|_{μ} := ⋃_{λ<μ} B_{λ} is convex in G′. If μ = 0, this is trivial as G′|_{μ} = ∅. If μ is a successor ordinal, then G′|_{μ} is convex by assumption (c). Finally, if μ is a non-zero limit, then G′|_{μ} is the nested union of the graphs ⋃_{λ′⩽λ} B_{λ′} with λ < μ; since these graphs are convex by (c), G′|_{μ} is also convex.

If V (G′)\V (G′|_{μ}) = ∅, we put σ := μ and terminate the construction of F′. Note that in this case G′|_{μ} = G′ (because, being convex, G′|_{μ} is induced in G′), so F′ satisfies (S1).

Assume now that V (G′)\V (G′|_{μ}) ≠ ∅. Let C_{μ} be a component of G′\G′|_{μ}, and set

\begin{aligned}H_{μ} & := G′ [ C_{μ} → G′|_{μ}] \\ S_{μ} & := H_{μ} ∩ G′|_{μ} . \end{aligned}

Then S_{μ} = G′|_{μ} [ v] for each vertex v ^{∈} C_{μ}, so S_{μ} is a simplex by Proposition 3.3.(iii). Since G′ is rayless and k-connected, S_{μ} is finite but has at least k vertices. (To be precise, the latter is true if and only if μ ≠ 0; note that in this case G′|_{μ}\S_{μ} ≠ ∅, since B_{0} ⊂ G′|_{μ} is not attached to C_{μ} by (a).)

We construct B_{μ} in ω steps (almost all of which will later turn out to be redundant), as the union of a nested sequence B_{μ}^{0} ⊂ B_{μ}^{1} ⊂ … of finite supergraphs of S_{μ} in H_{μ}. With B_{μ}^{0} := S_{μ}, let us assume that B_{μ}^{0}, …, B_{μ}^{n−1} have been defined for some n ⩾ 1. If B_{μ}^{n−1} is an attached simplex in H_{μ} (which is the case, for example, for n = 1), we pick a vertex v ^{∈} C_{μ}\B_{μ}^{n−1} such that B_{μ}^{n−1} = B_{μ}^{n−1} [ v], and set B_{μ}^{n} := B_{μ}^{n−1} ∪ { v }. Let us further define a set P′_{n} := ∅ for such n; this set will be needed as a ‘dummy’ in a recursion formula below. For the remainder of the construction of B_{μ}^{n}, we shall now assume that B_{μ}^{n−1} is not an attached simplex in H_{μ} (and in particular, that n > 1).

We first make B_{μ}^{n−1} induced in G′ by adding any missing edges, putting

B̃_{μ}^{n−1} := G′ [ B_{μ}^{n−1} ] .

Let us write E_{μ}^{n} for the set of edges we added; thus

E_{μ}^{n} = E(B̃_{μ}^{n−1}) ∖ E(B_{μ}^{n−1}) .

Next, we let P′_{n} be any inclusion-maximal set of independent B̃_{μ}^{n−1} – B̃_{μ}^{n−1} paths in H_{μ} whose endvertices x, y are non-adjacent in B̃_{μ}^{n−1}. Note that for each pair xy of endvertices in B̃_{μ}^{n−1} there are only finitely many such paths, by the definition of G′ and the remark following Proposition 4.1; since B_{μ}^{n−1} and hence the number of these pairs is finite, P′_{n} is also finite. Third, we let P′′_{n} be another finite set of B̃_{μ}^{n−1} – B̃_{μ}^{n−1} paths, this time in G itself, choosing k such paths x … y for each edge

xy ^{∈} (E_{μ}^{n} ∪ ⋃_{P^{∈}P′_{n−1}} E(P)) ∖ E(G)

in such way that all these paths are internally disjoint from each other and from every path in P′_{n}. (We assume here that P′_{n−1} has already been defined as a set of paths in B_{μ}^{n−1}.) Since G contains infinitely many independent x–y paths for every such pair xy (by definition of G′), such a set P′′_{n} does certainly exist. Moreover, every path of P′′_{n} lies in H_{μ}, because it can have at most one endvertex and no interior vertex in S_{μ} (recall that S_{μ} = B_{μ}^{0} ⊂ B_{μ}^{n−1}). Finally, we put P_{n} := P′_{n} ∪ P′′_{n}, and set

B_{μ}^{n} := B̃_{μ}^{n−1} ∪ ⋃ P_{n}

and

B_{μ} := ⋃_{n^{∈}ℕ} B_{μ}^{n} .

Let us prove that although we formally took infinitely many steps to construct it, B_{μ} is in fact finite. More precisely, let us prove that B_{μ}^{n+1} = B_{μ}^{n} for all sufficiently large n. Suppose the contrary holds. Since G′ is rayless and hence contains no infinite simplex, there exists an n_{0} ^{∈} ℕ such that B_{μ}^{n} is not an attached simplex in H_{μ} for any n ⩾ n_{0}. Thus P_{n} ≠ ∅ for arbitrarily large n. In fact, P_{n} ≠ ∅ for every n > n_{0}. For if P_{n} = P′_{n} ∪ P′′_{n} = ∅, then P′_{n+1} = ∅ by the maximality of P′_{n}. Moreover, B_{μ}^{n} = B̃_{μ}^{n−1}, so B_{μ}^{n} is induced in G′. But then E_{μ}^{n+1} = ∅, and hence P′′_{n+1} = ∅. Thus again P_{n+1} = ∅. By induction, this gives P_{n} = ∅ eventually for all n, a contradiction.

Notice that if n > n_{0} and P is a path in P_{n+1}, then at least one of the two endvertices of P lies in the interior of a path Q ^{∈} P_{n}: if P ^{∈} P′_{n+1}, this is a consequence of the maximality of P′_{n}, while for P ^{∈} P′′_{n+1} it follows from the definition of E_{μ}^{n+1}. (Recall that B̃_{μ}^{n−1} ⊂ B_{μ}^{n} is induced in G′, so any edge of B̃_{μ}^{n} that is not already an edge of B_{μ}^{n} must have one of its endvertices in B_{μ}^{n}\B̃_{μ}^{n−1} = ⋃ { Q̊ | Q ^{∈} P_{n} }.) Choosing a fixed such Q = Q(P) ^{∈} P_{n} for each P ^{∈} P_{n+1} and every n > n_{0}, let K be the graph with vertex set

V (K) := ⋃_{n>n_{0}} P_{n}

and edge set

E(K) := { P Q(P) | P ^{∈} P_{n+1} for some n > n_{0} } .

Since each of the sets P_{n} is finite, König’s Infinity Lemma implies that K contains a ray Q_{1}Q_{2} … with Q_{i} ^{∈} P_{n_{0}+i} for every i. By construction of K, the subgraph ⋃_{i^{∈}ℕ} Q_{i} of G′ contains a ray, contradicting the fact that G′ is rayless. This completes the proof that B_{μ} is finite.

Let us now check that our definition of B_{μ} complies with the conditions (a)–(c) for λ = μ. For a proof of (c) note that, by construction, the endvertices x, y of any B_{μ}–B_{μ} path P ⊂ H_{μ} are adjacent in B_{μ}: since x and y are contained in B_{μ}^{n} for some n, the existence of P would otherwise contradict the maximality of P′_{n+1}. By Proposition 3.3.(ii), therefore, B_{μ} is a convex subgraph of H_{μ}.

By Lemma 3.4.(ii) and our observation that G′|_{μ} is convex in G′ (and hence in G′ [ G′|_{μ} → S_{μ}]), this implies that ⋃_{λ′⩽μ} B′_{λ′} = G′|_{μ} ∪ B_{μ} is convex in G′, as required for (c).

In order to show (a) for λ = μ, let n ^{∈} ℕ be such that B_{μ} = B_{μ}^{n} = B_{μ}^{n+1}. Suppose that B_{μ} is attached in G′, i.e. that B_{μ} = B_{μ} [ v] for some vertex v ^{∈} G′\B_{μ}. As B_{μ} ∩ C_{μ} ≠ ∅ by the construction of B_{μ}, clearly v ^{∈} C_{μ}. Since B_{μ} is convex in H_{μ}, Proposition 3.3.(iii) implies that B_{μ} is a simplex. But then B_{μ} = B_{μ}^{n} is an attached simplex in H_{μ}, so our construction of B_{μ} prescribes that B_{μ}^{n+1} = B_{μ}^{n} ∪{ w } for some vertex w ^{∈} C_{μ}\B_{μ}^{n}, contrary to our assumption that B_{μ}^{n} = B_{μ}^{n+1}.

For a proof of (b), finally, notice that if xy ^{∈} E(B_{μ})\E(G) and λ(y) = μ, then there exists an n ^{∈} ℕ such that xy ^{∈} E_{μ}^{n} or xy ^{∈} E(P) for some P ^{∈} P′_{n}. The k independent x–y paths required for (b) are therefore contained in P′′_{n} or in P′′_{n+1}.

To complete our construction of the family F′ = (B_{λ})_{λ<σ}, it remains to observe that B_{μ}\G′|_{μ} ≠ ∅ for each μ; the construction therefore terminates after no more than |G′| steps.

Having noted earlier that F′ satisfies (S1), we observe further that the simplex S_{μ} coincides with B_{μ} ∩ G′|_{μ} for each μ < σ, so F′ satisfies (S2). Moreover, as S_{μ} is attached, it cannot contain any B_{λ} by (a), so F′ also satisfies (S3). Finally, it is easily checked that S_{μ} ⊂ B_{λ} for λ := max Λ(S_{μ}) (observe that S_{μ} has a vertex in B_{λ}\S_{λ} and, being a simplex, is not separated by S_{λ}), so F′ satisfies (S4). Therefore F′ is a simplicial tree-decomposition of G′.

As |S_{μ}| ⩾ k for every μ > 0, F′ is k-connected. To see that F′ is coherent, suppose that, for some μ < σ, S_{μ} is not attached to B_{μ}\S_{μ} or B_{μ}\S_{μ} is disconnected. In either case there exists a subsimplex S ⊂ S_{μ} which separates vertices x, y ^{∈} B_{μ}\S in B_{μ}. As S_{μ} is attached to C_{μ} and B_{μ}\S_{μ} ⊂ C_{μ}, S cannot separate x and y in H_{μ}. By Proposition 3.3.(iv), this contradicts the convexity of B_{μ} in H_{μ} noted above in the proof of (c).

To see that F′ is rayless, suppose that B_{λ_{0}}B_{λ_{1}} … is a ray in T_{F′}, without loss of generality chosen such that B_{λ_{0}} = B_{0}. Then S_{λ_{n+1}} ⊂ B_{λ_{n}} for each n, and S_{λ_{n+1}} has a vertex in B_{λ_{n}}\S_{λ_{n}}; let such a vertex v_{n} be chosen for each n. Now since F′ is coherent, each B_{λ_{n}} with n ⩾ 1 contains a v_{n−1}–v_{n} path P_{n} whose only vertex in S_{λ_{n}} is v_{n−1}. The union of all these paths P_{n} is a ray in G′, a contradiction.

We now come to the final step of the proof, the construction of a treedecomposition of G. For each λ < σ, let B_{λ}^{−} be the shadow of B_{λ} in T_{F′}; thus

B_{λ}^{−} = ⋃ { B ^{∈} F′ | B ⩽_{T_{F′}} B_{λ} } .

Recall that, by Proposition 3.2, each of these B_{λ}^{−} is a convex subgraph of G′. Let us define

G_{λ} := B_{λ}^{−} ∩ G

for each λ < σ, and set

F := (G_{λ})_{λ<σ} .

We shall prove that F is a tree-decomposition of G with the desired properties.

Since F′ satisfies (S1) with respect to G′, clearly F satisfies (S1) with respect to G. In order to check (S4), note that if μ < σ is given, and τ(μ) < μ is such that B_{τ(μ)}B_{μ} ^{∈} E(T_{F′}) (i.e., B_{τ(μ)} is the immediate predecessor of B_{μ} in T_{F′}), then G_{μ} ∩ G|_{μ} = G_{τ(μ)}. Thus, F is a tree-decomposition of G. (Note that F does not, in this form, satisfy (S3); however, this could easily be achieved by restricting F to those G_{λ} for which B_{λ} is a leaf in T_{F′}.)

To see that the factors in F are finite, recall that each B_{λ}^{−} is a finite union of finite graphs, and hence itself finite. Since B_{λ}^{−} ⊇ B_{0} ⊇ S_{1} for every λ, and |S_{1}| ⩾ k, any two factors G_{λ} ^{∈} F have at least k vertices in common; hence F is k-connected. As for the raylessness of F, recall that S_{μ}, and hence V (G_{μ} ∩ G|_{μ}) ⊇ V (S_{μ}), contains a vertex s with λ(s) = τ(μ) (taken in F′). Thus, while G_{μ} ∩ G|_{μ} is contained in G_{τ(μ)} (as pointed out above), G_{μ} ∩ G|_{μ} is not contained in G_{λ} for any λ < τ(μ), so G_{μ} is joined to G_{τ(μ)} when T_{F} is constructed. In other words, T_{F} is isomorphic to T_{F′} under the natural isomorphism mapping G_{λ} to B_{λ}. Since T_{F′} is rayless, this means that T_{F} too is rayless.

It remains to show that every G_{λ} is k-connected. Suppose not, and let U ⊂ V (G_{λ}) be a set of fewer than k vertices separating G_{λ}. Let C and C′ be distinct components of G_{λ} − U. Since G′ is k-connected, there exists a C–C′ path P in G′ avoiding U; as B_{λ}^{−} is convex in G′, we may assume that P ⊂ B_{λ}^{−}. Assuming further that C and C′ were suitably chosen, P thus consists of a single edge xy, say with λ(x) ⩽ λ(y). Then xy ^{∈} E(B_{λ(y)}) ∖ E(G). By (b) in the construction of F′, there are at least k independent x–y paths in B_{λ(y)} ∩ G ⊂ G_{λ}. One of these paths must avoid U, contrary to our assumption that x and y are in distinct components of G_{λ} − U. This completes the proof that G_{λ} is k-connected, for every λ < σ.

(ii)→(i). If G has a rayless and k-connected tree-decomposition F = (B_{λ})_{λ<σ} into finite k-connected factors, then G is clearly k-connected (induction on μ ⩽ σ for G|_{μ}).

Suppose G contains a ray R. As each factor in F is finite, Λ(R) must be infinite. Let

U := { B_{λ} | λ ^{∈} Λ(R) } ,

pick a vertex v(B_{λ}) ^{∈} R ∩ (B_{λ}\S_{λ}) from each B_{λ} ^{∈} U, and set

V := { v(B) | B ^{∈} U } .

Note that v(B) ≠ v(B′) for distinct B, B′ ^{∈} U, because λ(v(B)) ≠ λ(v(B′)).

Let T be the infinite subtree of T_{F} arising from the union of all the U–U paths in T_{F}. As T is rayless, it has a vertex B of infinite degree (Corollary 1.1).

By the construction of T, every edge incident with B in T lies on a B–U path in T. Hence, there is an infinite subset U′ of U such that B lies on the path in T_{F} between any two elements of U′. As B is finite, U′ can be chosen such that v(B′) /^{∈} B for any B′ ^{∈} U′. By Proposition 3.1, therefore, B separates any two vertices of

V′ := { v(B′) | B′ ^{∈} U′ }

in G. Since V′ is an infinite subset of V (R), this contradicts the fact that B is finite.

Hence G is rayless, as claimed. □

References

[1] R. Diestel, Graph decompositions: a study in infinite graph theory, Oxford University Press, Oxford 1990.

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

[3] R. Diestel, The end structure of a graph: recent results and open problems, submitted.

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

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

[6] R. Halin, Bounded graphs, in: (R. Diestel, Ed.) Directions in infinite graph theory and combinatorics (Annals of Discrete Mathematics), in press.

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

[8] 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.

[9] R. Schmidt, Ein Ordnungsbegriff für Graphen ohne unendliche Wege mit einer Anwendung auf n-fach zusammenhängende Graphen, Archiv der Mathematik 40 (1983), 283–288.

[10] P. D. Seymour and R. Thomas, An end-faithful counterexample, Proceedings of the AMS, to appear.

[11] J. Širáň, End-faithful spanning trees, paper given at the 1989 Cambridge Conference on Infinite Graph Theory and Combinatorics.

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

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