A Proof of the Bounded Graph Conjecture

Reinhard Diestel and Imre Leader

An infinite graph is called bounded if for every labelling of its vertices with natural numbers there exists a sequence of natural numbers which eventually exceeds the labelling along any ray in the graph. We prove an old conjecture of Halin, which characterizes the bounded graphs in terms of four forbidden topological subgraphs.

1. Introduction

Let σ, τ: ℕ → ℕ be two sequences of natural numbers. We say that σ dominates τ if σ(n) ⩾ τ(n) for every n greater than some n_{0} ^{∈} ℕ. Now let G be an infinite graph, and assume the vertices of G are labelled with natural numbers, say by f: V (G) → ℕ. Then each ray (one-way infinite path) R = x_{0}x_{1} … in G gives rise to a sequence τ_{R} := (f(x_{0}), f(x_{1}), …); we say that σ dominates R if σ dominates this sequence τ_{R}. We may then ask whether or not there exists a sequence σ: ℕ → ℕ which dominates all the rays in G simultaneously. If this is the case, we say that the labelling f of G is bounded by σ; if not, f is unbounded.

An unlabelled graph G is said to be bounded if every labelling of its vertices is bounded. Thus, G is bounded if and only if for every labelling f: V (G) → ℕ there exists a sequence σ: ℕ → ℕ which dominates every ray in G with respect to f. If not, G will be called unbounded.

Our main aim in this paper is to give a proof of what has become known as the ‘bounded graph conjecture’ [ 5 ]. This conjecture, proposed by Halin in 1964 (see [ 5 ]) but first published in [ 4 ], characterizes the bounded graphs by the exclusion of four simple prototypes of unbounded graphs as topological subgraphs. Not surprisingly, this characterization has some fundamental implications for the concept of boundedness.

Before we state the bounded graph conjecture in detail, let us look at a few examples of bounded and unbounded graphs. K_{ω}, the complete graph on a countably infinite set of vertices, is clearly unbounded: choose any labelling that uses infinitely many distinct labels, and there will be rays whose labellings grow faster than any fixed ℕ → ℕ sequence.

Another trivial example of an unbounded graph is the following. For a cardinal κ, let I_{κ} denote the disjoint union of κ rays. Then I_{κ} is unbounded for every κ ⩾ 2^{ω}. Indeed, since there are only 2^{ω} different ℕ → ℕ sequences, we can accommodate every possible sequence as the labelling of one of the rays of I_{κ}. The overall labelling of I_{κ} then is clearly unbounded, and so I_{κ} is unbounded.

This trivial uncountable example of an unbounded graph is in fact the only uncountable aspect of the whole bounded graph problem: as we shall see, the task of classifying the bounded or unbounded graphs without uncountably many disjoint rays is an entirely ‘countable’ problem. (Indeed, we shall find that such a graph is bounded if and only if all its countable subgraphs are bounded (Corollary 7.3).)

Let us then look at some further countable examples. A graph with only countably many rays is bounded, due to the following well-known observation:

Lemma 1.1. Every countable family of sequences σ_{n}: ℕ → ℕ (n ^{∈} ℕ) is dominated by a common sequence σ: ℕ → ℕ.

Proof. For each n ^{∈} ℕ, set σ(n) := max { σ_{0}(n), …, σ_{n}(n) }. □

For example, a single ray contains only countably many distinct rays as subgraphs (namely, all its ‘tails’), and is therefore bounded.

A similar argument shows that, more generally, every locally finite connected graph G is bounded. Indeed, given a labelling f and any fixed vertex v of G, it is easy to construct a sequence σ_{v} which dominates all the rays in G starting at v; then Lemma 1.1 provides a sequence which dominates all these (countably many) sequences σ_{v}, and hence bounds f.

The example of K_{ω} may suggest that countable graphs have to be dense in order to be unbounded. However, this is not the case. T_{ω}, the tree of countably infinite regular degree,* is also unbounded. To show this, we have to find a labelling f: V (T_{ω}) → ℕ such that no ℕ → ℕ sequence dominates all the rays in T_{ω} with respect to f. This is easily done. In fact, all we ask is that f be injective, i.e. that all the vertices of T_{ω} be labelled differently. Given σ: ℕ → ℕ, we then choose a ray in T_{ω} as follows. Let x_{0} be any vertex of T_{ω} whose label is greater than σ(0). Since f is injective, x_{0} has a neighbour x_{1} whose label exceeds σ(1). Continuing in this manner, we find a ray x_{0}x_{1} … ⊂ T_{ω} such that f(x_{n}) > σ(n) for every n, so this ray is certainly not dominated by σ.

The following example of an unbounded graph is based on the same idea. Let B be the graph obtained from a ray v_{0}v_{1} … by adding, for each n ^{∈} ℕ, a countably infinite set of independent v_{3n+1}–v_{3n+3} paths of length 2 (Fig. 1). Any subdivision of B will be called a bundle graph. (See §2 for the definition of subdivision etc.)

To show that B is unbounded, let f be any injective labelling of B, and assume we are given a sequence σ: ℕ → ℕ. Let us specify a ray R = x_{0}x_{1} … as follows. Put x_{0} := v_{0} and x_{1} := v_{1}. For x_{2}, we have an infinite choice of neighbours of v_{1}, all labelled differently. We may thus choose as x_{2} a neighbour of v_{1} whose label is greater than σ(2). We continue with x_{3} := v_{3} and x_{4} := v_{4}, where again we have an infinite choice for x_{5}. Proceeding in this manner, we

* This means that every vertex of T_{ω} has exactly ω neighbours; see §2.

FIGURE 1. The prototype bundle graph B

may choose R in such a way that f(x_{n}) exceeds σ(n) for every third value of n, and thus σ fails to dominate R.

Our last example is similar to B. Let F be the graph obtained from a ray V = v_{0}v_{1} … by adding disjoint rays P_{2}, P_{4}, P_{6}, … with P_{k} ∩ V = { v_{k} }, and joining v_{2n+1} to all the new vertices of P_{2n+2} for every n ^{∈} ℕ (Fig. 2). Any subdivision of F will be called a fan graph.

FIGURE 2. The prototype fan graph F

F is again unbounded, the proof being essentially the same as for B. Indeed, given any injective labelling f: V (F) → ℕ and any sequence σ: ℕ → ℕ, we can easily find a ray R through F whose labels exceed the corresponding values of σ again and again. All we have to ensure when defining R is that we start at v_{0}, and never use an edge of one of the paths P_{k} in its ‘upward’ direction. (This would force us to trace out the entire tail of P_{k}, leaving us unable to return to a vertex of type v_{2n+1} with an infinite choice ahead.)

It is perhaps remarkable that F can be made bounded by what would seem to be an inessential change. If the ‘fans’ in F are flipped horizontally, i.e. if the vertices v_{2n+1} are joined to all the vertices of P_{2n} rather than to those of P_{2n+2} (add a ray P_{0}), the resulting graph is bounded. (This example is due to Halin; he found it so discouraging that it prompted him to doubt the possibility of a proof of his conjecture by elementary methods [ 5 ].)

We are now ready to state Halin’s conjecture. If a graph G has a subgraph isomorphic to a subdivision of a graph X, we say that X is a topological subgraph of G.

Bounded Graph Conjecture. (Halin) Assume the Continuum Hypothesis. A graph is bounded if and only if it contains none of the following graphs as a topological subgraph: I_{ω_{1}}; T_{ω}; B; F.

The forward implication of the conjecture should be obvious: we have seen that the graphs I_{2^{ω}}, T_{ω}, B and F are all unbounded; these proofs remain essentially the same for subdivisions of the latter three graphs (and identical for I_{ω_{1}} = I_{2^{ω}}), and it is clear that no bounded graph can have an unbounded subgraph.

A word concerning the Continuum Hypothesis (CH). When Halin originally proposed the bounded graph conjecture (in connection with Rado’s seminal paper on Universal graphs and universal functions [ 9 ]), it was understood to refer to countable graphs only, and T_{ω}, B and F were the only forbidden (topological) subgraphs. There was no mention of CH. Halin later strengthened the conjecture to include graphs of any cardinality, which resulted in the additional exclusion of I_{2^{ω}}. This in turn suggested the assumption of CH, as it seemed unclear whether or not I_{κ} is bounded when κ is a cardinal strictly between ω and 2^{ω}.

In fact, it is well-known among set theorists that this latter question is independent of the usual axioms of set theory. Martin’s Axiom, for example, implies that every I_{κ} with κ < 2^{ω} is bounded, but it is consistent with ZFC that there exist κ < 2^{ω} for which I_{κ} is unbounded.

It should be stressed that our proof of the bounded graph conjecture is entirely free from such set theoretic considerations. To make this possible, we take the following (standard) approach. We shall define a cardinal 𝔟 in such a way that it is the least cardinal κ for which I_{κ} is unbounded (whatever the value of that cardinal may be), and then prove—without assuming CH—that a graph is bounded if and only if it contains none of I_{𝔟}, T_{ω}, B or F as a topological subgraph. Since ω < 𝔟 ⩽ 2^{ω}, and hence ω_{1} = 𝔟 = 2^{ω} with CH, this in particular implies the bounded graph conjecture as stated above.

It turns out that we need to show very little about 𝔟 to make this approach work. However, any reader who prefers to work with countable sets and is willing to accept CH will lose nothing by substituting ‘countable’ whenever he reads ‘< 𝔟’.

Before we get down to the proof of the bounded graph conjecture, let us look at some of its immediate implications. (See also §7.) As a first corollary, the conjecture implies that subdivisions of bounded graphs are again bounded, and that subdivisions of unbounded graphs are unbounded. The first of these two statements may not be unexpected: for countable graphs it follows without much effort from the definition of boundedness. The second assertion is more surprising. Indeed, it would seem that there should be graphs which are unbounded largely because they are dense (as our example of K_{ω}), so that subdividing their edges sufficiently often might make them bounded.

Together with the obvious fact that subgraphs of bounded graphs are bounded, the assertion that subdivisions of unbounded graphs are again unbounded is equivalent to saying that boundedness is closed under taking topological subgraphs. We shall also derive a forbidden minor version of the bounded graph conjecture (Theorem 7.7), together with a corollary saying that boundedness is closed under taking minors (with finite branch sets).

Another consequence of the bounded graph conjecture is the fact that a graph is bounded if and only if all its countable subgraphs are bounded— unless, of course, it contains uncountably many disjoint rays, in which case it is trivially unbounded (assuming CH). Thus, boundedness is shown to be an essentially ‘countable’ property, irrespective of the cardinality of the graph considered.

Finally, the bounded graph conjecture implies that if a countable graph admits any unbounded labelling at all, then all its injective labellings are unbounded. (Recall that the latter is true for subdivisions of T_{ω}, and for bundle and fan graphs.) It is therefore never difficult to find an unbounded labelling for an unbounded graph: its unboundedness lies properly in its structure, not in the complication of any particular labelling.

On the face of it, the bounded graph conjecture seems rather a bold conjecture to make. There appears to be nothing special about the four unbounded graphs which it claims are the only prototypes—indeed it would seem that playing with a few examples should reveal many more similar ‘minimal’ unbounded graphs. This may partly explain the fact that over the last 25 years there seem to have been few serious attempts at proving the conjecture.

Halin himself published his own partial results only very recently. In a paper written in 1986 [ 4 ], he proves the bounded graph conjecture for countable trees. Note that of the four forbidden graphs from the conjecture this involves only T_{ω}; graphs of the other three types cannot even occur in a countable tree. A few years later, Halin extended this theorem to graphs whose blocks are rayless [ 5 ] (see also [ 2 ]). The extended result still involves only three of the four forbidden configurations, as fan graphs cannot occur. A very recent result of Halin, also found in [ 5 ], confirms the bounded graph conjecture for graphs not containing an infinite set of disjoint rays. (This last theorem builds on Halin’s well-known structural characterization of these graphs by ‘chain-like’ decompositions.)

The following may help to motivate the bounded graph conjecture a little better, taking some of the arbitrariness out of its list of forbidden configurations. (It will also be used later, for a proof of Lemma 2.3.) Let G be a connected unbounded graph. Since locally finite connected graphs are bounded, G has a vertex v of infinite degree. Let us assume that every edge incident with v can be extended to a ray (which is not an enormous assumption), and let R_{0}, R_{1}, … be an infinite set of rays all starting at v. Can R_{0}, R_{1}, … be chosen pairwise independent (i.e., disjoint except for v)? If so, they might be seen as the beginning of a subdivided T_{ω} in G, and we might try to find similar rays starting at other vertices of the R_{n} to continue the construction.

If the rays R_{0}, R_{1}, … cannot be chosen independent, it seems reasonable to expect that we can choose them in such a way that there exists a finite set of vertices, and hence a single vertex w, which each of them meets. We may now apply König’s theorem (see §2) to combine suitable initial segments of the rays R_{n} into what might be the first ‘bundle’ of a bundle graph, or the first ‘fan’ of a fan graph in G.

Indeed, let us choose initial segments P_{n} of the R_{n} as follows. Let P_{0} be the initial segment of R_{0} that ends at w. Having defined P_{0}, …, P_{n} for some n ^{∈} ℕ, let P_{n+1} be the initial segment of R_{n+1} which ends at the first vertex of R_{n+1} that is in P_{0} ∪ … ∪ P_{n}. Let this vertex be called w_{n+1}, and let k(n + 1) be the minimal k for which w_{n+1} ^{∈} P_{k}. Call P_{k(n+1)} the predecessor of P_{n+1}.

Let T be the tree whose vertices are the paths P_{n} (n ^{∈} ℕ), and in which each vertex P_{n} (for n = 1, 2, …) is joined by an edge to its predecessor P_{k(n)}. By König’s theorem, T contains a ray or has a vertex of infinite degree. If T has a vertex of infinite degree, P_{k} say, then P_{k} contains a vertex x such that w_{n} = x for infinitely many n > k. The paths P_{n} with w_{n} = x are pairwise independent (i.e., disjoint except for v and x), and they form a ‘bundle’ (Fig. 3).

On the other hand if T contains a ray, without loss of generality starting at P_{0}, then the union of the paths P_{n} ⊂ G which are the vertices of this ray are easily seen to form a ‘fan’ (Fig. 3). (Note that, by the construction of T, if P_{m} succeeds P_{n} on the ray in T then m > n, so P_{n} is the predecessor of P_{m}.)

FIGURE 3. A bundle or a fan on a path P_{k} = v … w

The main purpose of the above considerations is to persuade the reader that fans and bundles are indeed natural ingredients of unbounded graphs. It must be said, however, that these considerations have not taken us anywhere near a proof of the bounded graph conjecture. Indeed, one might well find various fans and bundles in an unbounded graph: the problem is that, in general, they will be far from disjoint. Our task will thus be to prove that unbounded graphs must contain fans and bundles in such abundance that it is possible to select an infinite set of them as tidily threaded on a ray as in the graphs B and F.

The paper is organized as follows. We begin with a short section on notation and basic lemmas. This is followed by a section on normal spanning trees, the main structural tool in our proof, and another which contains two simple Ramsey-type lemmas concerning partitions of T_{ω}. The bounded graph conjecture is then proved in Sections 5 and 6, with a concluding section listing some immediate corollaries.

2. Notation and basic lemmas

All the graphs considered in this paper are undirected and simple, i.e. have neither loops nor multiple edges. The axiom of choice is assumed throughout the paper. The set of natural numbers, ℕ, includes 0. The first infinite ordinal is denoted by ω, the first uncountable ordinal by ω_{1}.

Let G be a graph. The edge set of G will be denoted by E(G), its vertex set by V (G), and its number of vertices by |G|. When H is a subgraph of G, denoted by H ⊂ G, we may simply say that G contains H. If xy is an edge (for x, y ^{∈} V (G)), then y is a neighbour of x, and the two vertices are adjacent. The neighbourhood of a vertex is the set of its neighbours. G is locally finite if the degree of each vertex, the number of its neighbours, is finite.

A path may be finite or infinite; its length is its number of edges. A path of length 0 is trivial. A one-way infinite path is a ray, and a graph is rayless if it contains no ray. Any infinite connected subgraph of a ray R is a tail of R. We usually write a path as the sequence of its vertices, which gives these a natural order. It then makes sense to say that a path starts or ends at some particular vertex, that one vertex precedes another on it, and so on.

If P = x_{1} … x_{n} is a path, we write P̊ for the interior of P, the subpath x_{2} … x_{n−1}. The vertices of P̊ are the inner vertices of P. Similarly, if 1 ⩽ i ⩽ j ⩽ n, we set 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 and for trees (so that xT y is the unique path from x to y in the tree T), and for the concatenation of paths. For example, if x is a common vertex of two paths P and Q, then P xQ denotes the ‘walk’ P x ∪ xQ. The path P x_{i} defined above is an initial segment of P, and P an extension of P x_{i}. Note that a finite path is an initial segment of itself.

For X, Y ⊂ G, we call a finite path P ⊂ G an X–Y path if its endvertices are in X and Y, respectively, and its inner vertices lie in G ∖ (X ∪ Y). When X or Y consists of only one vertex, we speak of (say) x–Y or X–y paths rather than { x } –Y or X– { y } paths.

If X ⊂ V (G), we write G [ X] for the subgraph of G induced by the vertices in X. For H ⊂ G and x ^{∈} G, we write H [ x] for the subgraph of H induced by those of its vertices y for which G contains an x–y path that has no vertices in H other than y. In particular, if x is a vertex of H then H [ x] is just the singleton { x }. On the other hand, if x /^{∈} H and C is the component of G\H containing x, then H [ x] contains precisely those vertices of H that have a neighbour in C.

Two or more paths are independent if their interiors are disjoint. If A, B and X are subgraphs of G or subsets of V (G), we say that X separates A from B in G if every A–B path in G contains a vertex of X. We use this notation even when A and B are not disjoint; of course, X must then contain A ∩ B.

When T is a tree (an acyclic connected graph), we shall often pick a root r ^{∈} V (T), and call T rooted at r. This induces a natural partial order on V (T), in which x ⩽ y iff x lies on the unique r–y path rT y in T. Informally, we think of this order as expressing the vertices’ heights in T; we may then speak of y being above x if y > x, call it an upper neighbour of x if it is above x and adjacent to it, and so on.

Note that, for each vertex z ^{∈} T, the set of all vertices x ⩽ z is linearly ordered; the subgraph it spans in T will be denoted by ⌊z⌋. The down-closure ⌊U⌋ of a set U ⊂ V (T) is the graph ⋃ { ⌊u⌋ | u ^{∈} U } ⊂ T. For any vertex v of T, the subtree of T spanned by all the vertices x ⩾ v will be denoted by T^{⩾v}. Similarly, we write T^{>v} for T^{⩾v} ∖ { v }.

If T ⊂ G and V (T) = V (G), then T is said to span the graph G. The order ⩽ on V (T) thus becomes an order on V (G); if we wish to be more specific, we may denote it by ⩽_{T} .

A subdivision of a graph X, denoted by TX, is any graph obtained from X by replacing its edges with independent paths of lengths ⩾ 1. The original vertices of X are then called the branch vertices of the TX; the other vertices of the TX are its subdividing vertices. X is a topological subgraph of any graph containing a TX. If X is a tree rooted at some vertex r, then any TX will again be assumed to be rooted at r; the order on V (X) is thus embedded in the tree order on the vertices of the TX.

The following definition and lemma will not be needed until §7. They are included here for completeness, but the reader may wish to skip straight to König’s theorem further below.

In analogy to our notation concerning topological subgraphs, we say that a graph H is an HX (where ‘H’ comes from ‘homomorphism’) if its vertex set admits a partition { V_{x} | x ^{∈} V (X) } into subsets V_{x} spanning connected subgraphs in H so that H contains a V_{x}–V_{y} edge if and only if x and y are adjacent in X. The sets V_{x} are called the branch sets of H. A graph X′ is said to be a minor of H if H has a subgraph H′ such that H′ = HX′ (or, equivalently, if H = HX with X′ ⊂ X).

Lemma 2.1. Let X be a topological subgraph of a graph G. If X is countable or locally finite, then X is a minor of G with all branch sets finite.

Proof. By assumption, the components of X all have countable vertex sets; choose an enumeration for each of them. Let H be a TX contained in G. For each x ^{∈} V (X), let V_{x} be the subset of V (H) that consists of x and any subdividing vertices on x–y edges of X for which y precedes x in their common component of X. Note that each V_{x} is finite, and that it spans a connected subgraph in H. Hence, H is an HX as required. □

The following theorem of König [ 7 ], a simpler version of his well-known Infinity Lemma, is a standard tool which we shall use frequently:

König’s Theorem. Every infinite connected graph contains either a vertex of infinite degree or a ray. □

We conclude with some less standard teminology.

It will often be useful to be able to combine several sequences of natural numbers into one fast growing sequence which dominates them all. For σ: ℕ→ℕ, let σ′, σ′′: ℕ→ℕ be defined by setting σ′(n) := max{ σ(0), …, σ(n) } and σ′′(n) := σ′(2n). Then σ′′ dominates σ′, which in turn dominates σ. The sequence σ′′ will be called the majorant of σ. More generally, let F be a family of ℕ → ℕ sequences dominated simultaneously by a sequence σ. We shall then also refer to the majorant σ′′ of σ as a majorant of the family F. Note that, by Lemma 1.1, every countable family of ℕ → ℕ sequences has a majorant.

The majorant of a single sequence is thus obtained by first making it monotonically increasing and then doubling its growth rate. It therefore ‘catches up’ with the original sequence even when shifted forward by any constant number of terms. This is the idea behind the following lemma, which is essentially due to Halin [ 5 ]:

Lemma 2.2. Let F be a family of ℕ → ℕ sequences, and let G be a graph with a labelling V (G) → ℕ. If R, R′ ⊂ G are rays sharing a tail, and if some σ ^{∈} F dominates R, then any majorant of F dominates R′. □

Let a and b be distinct vertices of a graph G. The union of an infinite set of independent a–b paths of lengths ⩾ 2 will be called a bundle from a to b, or an a–b bundle. The interior of any of those paths is a fibre of the bundle; note that these fibres are pairwise disjoint. The interior of a bundle is the union of its fibres. An a–b bundle B is said to be on a path P if B ∩ P = { a, b }, a precedes b on P, and aP b has length at least 2. If { B_{1}, …, B_{n} } is a (possibly empty) set of disjoint bundles on a common path P, arranged in such a way that the first vertex of P is in none of the B_{i} and both vertices of B_{i} ∩ P precede both vertices of B_{i+1} ∩ P on P for all i < n, then the union of P and the B_{i} is a partial bundle graph on P.

Similarly, the union of a ray R with initial vertex b and infinitely many paths from a vertex a /^{∈} R to R ∖ { b } is called a fan from a to b, or an a–b fan, if those paths are pairwise disjoint except for a and have no inner vertices on R. The ray R in such a fan is called its spine; the a–R paths are its spokes. The interior of a fan F from a to b is the graph F ∖ { a, b }. F is said to be on a path P if F ∩ P = { a, b } and a precedes b on P. If { F_{1}, …, F_{n} } is a (possibly empty) set of disjoint fans on a common path P, arranged in such a way that the first vertex of P is in none of the F_{i} and both vertices of F_{i} ∩ P precede both vertices of F_{i+1} ∩ P on P for all i < n, then the union of P and the F_{i} is a partial fan graph on P.

Using these terms, we can now write down as a lemma a precise summary of the observations we made at the end of the Introduction. The proof of the lemma was sketched there; the details are left to the reader.

Lemma 2.3. Let a and b be distinct vertices of a graph G, and let P be an infinite set of a–b paths in G whose second vertices are pairwise distinct. The union ⋃ P of these paths then contains a bundle B or a fan F. Moreover:

(i) The bundle B can be chosen as an a–x bundle on a path P ^{∈} P (where x is some vertex on P), and so that every a–x path in B is an initial segment of a path in P.

(ii) The fan F —with spine R, spokes S_{0}, S_{1}, …, and S_{n} ∩ R =: { v_{n} } for each n—can be chosen so that v_{n} precedes v_{m} on R whenever n < m, and each of the paths S_{n}v_{n}Rv_{n−1} is an initial segment of a path in P (where v_{−1} is the starting vertex of R). □

3. Normal spanning trees

In this section we introduce and develop the main structural tool for our proof, the concept of a normal spanning tree. A rooted spanning tree T of a graph G is called 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 either 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’.

It is easy to see that all finite connected graphs have normal spanning trees (obtained, for example, by a ‘depth-first search’). Jung [ 6 ] characterized the infinite graphs having normal spanning trees; his characterization implies that every countable connected graph contains such a tree. Starting from Jung’s result and using the theory of simplicial decompositions of graphs—see [ 1 ]— Halin [ 3 ] was able to prove the following:

Theorem 3.1. (Halin) If G is connected and G ⊉ TK_{ω}, then G has a normal spanning tree.

When we come to prove that an unbounded graph G must contain one of the four topological subgraphs listed in the bounded graph conjecture, we may thus assume that G has a normal spanning tree: if not, it would contain a TK_{ω}, and hence a TT_{ω}, as desired.

We now collect together a number of simple facts about normal spanning trees to be used later. All these are easy to prove, and they should help the reader develop an intuition for the properties of a normal spanning tree.

Let G be a fixed graph, and assume that G contains a normal spanning tree T with root r. Any reference to an order on the vertices of G (such as ‘above’, ‘below’, down-closures ⌊x⌋ and so on) will be assumed to refer to the order ⩽_{T} induced by T. A ray in G will be called a normal ray if it starts at r and is contained in T. The union of all normal rays, clearly a subtree of T, will be denoted by T′.

Our first lemma translates the local defining property for T (that every edge of G runs vertically along T) into a more global separation property of G:

Lemma 3.2. Let x, y ^{∈} V (G). Then ⌊x⌋ ∩ ⌊y⌋ = ⌊inf { x, y }⌋ separates x from y in G.

Proof. Let P = x_{1} … x_{n} be an x–y path in G, and put z := inf { x, y }; we have to show that P meets ⌊z⌋. This is trivial if x and y are comparable, so let us assume they are incomparable. Let w be the upper neighbour of z such that w ⩽ x. Then w ⩽̸ y; let x_{i} be the last vertex of P with w ⩽ x_{i}. Then x_{i+1} ^{∈} ⌊z⌋, because T is normal. □

Note that if x ^{∈} T′ then ⌊x⌋ ⊂ T′. Lemma 3.2 thus implies the following:

Lemma 3.3. If P = x … y is a T′–T′ path in G, then x and y are comparable in S.

Proof. If x and y are incomparable, then neither of them is in ⌊x⌋ ∩ ⌊y⌋, and so P̊∩ ⌊x⌋ ∩ ⌊y⌋ ≠ ∅ by Lemma 3.2. Since ⌊x⌋ ∩ ⌊y⌋ ⊂ T′, this means that P is not a T′–T′ path. □

Note that Lemma 3.2 does not imply that the interior of an x–y path meets ⌊x⌋ ∩ ⌊y⌋. The T′–T′ path in Lemma 3.3, for example, may have a non-empty interior lying in G\T′ somewhere above x and y.

Let S be a subtree of T rooted at r. (In applications, S will be either a normal ray or equal to T′.) Our next lemma says that any vertex of S which is ‘directly accessible’ from some vertex x /^{∈} S (by a path in G whose interior avoids S) must lie below x.

Lemma 3.4. Let S be a subtree of T rooted at r, and let x ^{∈} V (G). Then S [ x] ⊂ ⌊x⌋.

Proof. If x ^{∈} S, then S [ x] = { x } ⊂ ⌊x⌋. If x /^{∈} S, let P = x … y be an x– S path in G. By Lemma 3.2, P meets ⌊x⌋ ∩ ⌊y⌋ ⊂ S, while P̊∩ S = ∅ by the choice of P. Hence P ∩ ⌊x⌋ ∩ ⌊y⌋ = { y }, so y ^{∈} ⌊x⌋ as required. □

Lemma 3.4 implies that, if x is a vertex and R is a normal ray in G, the vertex set of R [ x] is a finite chain in ⩽_{T}. Let us define the R-height of x, denoted by ht(x; R), to be the unique maximal vertex of R [ x]. For example, the R-height of a vertex h ^{∈} R is h itself; the other vertices of R-height h are precisely those vertices which lie above h but not above any vertex of h̊R.

The concept of height will provide essential help in organizing our constructions of subgraphs of G such as fan and bundle graphs. For H ⊂ G or H ⊂ V (G), we shall say that the R-height of (the vertices in) H is bounded if R has a vertex h such that ht(x; R) ⩽ h for every vertex x ^{∈} H. Another subgraph H′ ⊂ G (or H′ ⊂ V (G)) is H-clear with respect to R if the R-height of each vertex of H′ is strictly greater than the R-height of every vertex in H. Then, for example, if we are trying to find a fan graph in G and H is a partial fan graph constructed so far (on the path P, say), we shall aim to extend P into H′ and continue our construction there; we can then be sure that fans constructed at later stages will not interfere with earlier fans.

The first assertion in our next lemma is immediate from the definition of R-height. The second is a consequence of the fact that, by definition, the graph R [ x] coincides for all vertices x in a common component of G\R.

Lemma 3.5. Let x, y ^{∈} G, and let R be a normal ray.

(i) If y ^{∈} R [ x], then ht(x; R) ⩾ y = ht(y; R).

(ii) If x and y are in a common component of G\R, then ht(x; R) = ht(y; R). □

If R and R′ are normal rays, and if x ^{∈} R\R′ and y ^{∈} R′\R, then R ∩ R′ separates x from y in G (by Lemma 3.2). This observation extends to any pair of vertices whose R-height and R′-height, respectively, is sufficiently large:

Lemma 3.6. Let R and R′ be distinct normal rays; set z := max (R ∩ R′). Suppose that x, y ^{∈} V (G) are such that ht(x; R) > z and ht(y; R′) > z. Then ⌊z⌋ = R ∩ R′ separates x from y in G.

Proof. Write u := ht(x; R) and v := ht(y; R′), and let P be any x–y path in G. Moreover, let x … u be an x–R path and y … v a y–R′ path in G. Since the walk u … xP y … v meets R ∩ R′ (by Lemma 3.2) but neither x … u nor y … v meets R ∩ R′ (by definition), P meets R ∩ R′ as claimed. □

Our next lemma asserts that if the R-height of x /^{∈} R is sufficiently large, then its R′-height is the same as that of the vertices on R\R′ itself, namely z = max (R ∩ R′).

Lemma 3.7. Let R and R′ be distinct normal rays, z := max (R ∩ R′), and x ^{∈} V (G). If ht(x; R) > z then ht(x; R′) = z.

Proof. Let P be an x–R path in G whose last vertex y is above z. Then P yRz is an x – (R ∩ R′) path, so ht(x; R′) ⩾ z by definition. Now if ht(x; R′) > z then Lemma 3.6, applied with y = x, would give that ⌊z⌋ separates x from x, a contradiction. Hence ht(x; R′) = z, as claimed. □

If R is a normal ray and H is any subgraph of G, let us say that the Rheight of H tends to infinity if for each h ^{∈} R only finitely many vertices of H have R-height ⩽ h. Lemma 3.7 then has the following immediate consequence:

Lemma 3.8. If R and R′ are distinct normal rays, and if the R-height of H ⊂ G tends to infinity, then the R′-height of H is bounded. □

If R is any ray in G and R′ is a normal ray, let us say that R follows R′ if |R ∩ R′| = ∞.

Lemma 3.9. Every ray in G follows a unique normal ray.

Proof. Let R ⊂ G be a ray. By Lemma 3.6, R can follow at most one normal ray. We show that such a ray exists, by constructing a normal ray x_{0}x_{1} … which R meets infinitely often. Let us assume that R starts at the root r of T; since this can be achieved by adding or deleting finitely many vertices of R, there will be no loss of generality.

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}. Since R can pass through ⌊x_{n}⌋ only finitely often, Lemma 3.2 implies that x_{n} has a unique upper neighbour y in T such that R has infinitely many vertices above y; 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}, … }. (For the existence of such a vertex, 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}. Hence y and x_{m} must be incomparable. By definition of x_{m}, yR contains a vertex x above x_{m}. By Lemma 3.2, then, yR meets

⌊x⌋ ∩ ⌊y⌋ ⊂ ⌊x_{m}⌋ = { x_{0}, …, x_{m} } ,

contrary to the choice of x_{n}. □

Note that, since normal rays are contained in T′, Lemma 3.9 implies in particular that G\T′ is rayless.

Our next lemma says that if a ray R follows a normal ray R′, then, in terms of R′-height, the vertices of R behave like those of R′ itself:

Lemma 3.10. Let R ⊂ G be a ray, and let R′ be the normal ray it follows. Then the R′-height of R tends to infinity.

Proof. Let x ^{∈} R′ be given; we have to show that at most finitely many vertices of R have R′-height ⩽ x. Let U := { v ^{∈} V (G) | ht(v; R′) ⩽ x }. Then ⌊x⌋ separates x̊R′ from U; recall that R′ [ v] ⊂ ⌊x⌋ for v ^{∈} U, by definition of ht(v; R′). Since R meets xR′ infinitely often, this implies that V (R) ∩ U is finite. □

Our last lemma shows how vertices with neighbourhoods of unbounded R-height can be used to find a copy of TK_{ω} in G.

Lemma 3.11. Let R be a normal ray.

(i) If the neighbourhood of a vertex x ^{∈} G has unbounded R-height, then x is on R.

(ii) If G has infinitely many vertices with neighbourhoods of unbounded Rheight, then G contains a TK_{ω}.

Proof. (i) If x is not in R, then the R-height of each of its neighbours is at most its own R-height, by Lemma 3.5.

(ii) Starting with X_{0} := ∅, let us define inductively a nested sequence X_{0} ⊂ X_{1} ⊂ … of subgraphs of G so that, for each n, X_{n} ≃ TK_{n} and the neighbourhood of any branch vertex of X_{n} has unbounded R-height. Let n > 0, and suppose that X_{n−1} ≃ TK_{n−1} has already been defined. Let x_{1}, …, x_{n−1} be the branch vertices of X_{n−1}; the neighbourhoods of these vertices all have unbounded R-heights. Since X_{n−1} is finite, G\X_{n−1} contains a vertex x_{n} whose neighbourhood has unbounded R-height.

Let us define independent paths P_{1}, …, P_{n−1} joining x_{n} to x_{1}, …, x_{n−1}, respectively. Let i ^{∈} { 1, …, n − 1 } be given, and assume that P_{j} has been defined for all j < i. Let y_{i} and y_{n} be neighbours of x_{i} and x_{n}, respectively, whose R-heights z_{i} and z_{n} exceed the R-heights of all the vertices in

X_{n}^{i−1} := X_{n−1} ∪ ⋃_{j<i} P_{j} .

Let y_{i} … z_{i} be a y_{i}–R path and y_{n} … z_{n} a y_{n}–R path in G. Note that the vertices on these two paths have uniform R-heights of z_{i} and z_{n}, respectively. Let P_{i} be an x_{i}–x_{n} path whose interior is contained in the walk y_{i} … z_{i}Rz_{n} … y_{n}. Then the vertices of P̊_{i} have R-heights between z_{i} and z_{n}, so P̊_{i} avoids X_{n}^{i−1}.

Putting

X_{n} := X_{n−1} ∪ ⋃_{i<n} P_{i} ,

we see that X_{n} ≃ TK_{n} as intended. Moreover, the branch vertices of X_{n} include those of X_{n−1}, and they all have neighbourhoods of unbounded R-height. This completes the induction step. It is clear that ⋃_{n^{∈}ℕ} X_{n} is isomorphic to TK_{ω}.

□

4. Partitions of T_{ω}

In this section we collect for convenience two simple Ramsey-type lemmas, which will be needed repeatedly later.

Both our lemmas are about finding TT_{ω} subtrees in a TT_{ω}. If T ≃ TT_{ω}, a colouring of T will be any map whose domain is the set of branch vertices of T; the images of such a colouring are called colours. T is monochromatic (or red, blue etc.) if all its branch vertices are coloured by (mapped to) the same colour (red, blue etc.), and T is injectively coloured if no two of its branch vertices have the same colour.

The proof of our first lemma is straightforward.

Lemma 4.1. If T is a rooted TT_{ω} with a red-blue colouring, then T contains either a red TT_{ω} of the form T^{⩾v} (for some branch vertex v of T) or a blue TT_{ω} (whose minimal vertex is one of its branch vertices). □

As a point of reference, let T^{∗} be a fixed copy of a rooted T_{ω}, given with an enumeration e_{1}^{∗}, e_{2}^{∗}, … of its edges such that, for each n ^{∈} ℕ, the graph T_{n}^{∗} ⊂ T^{∗} consisting of the root of T^{∗} and the edges e_{1}^{∗}, …, e_{n}^{∗} (together with their endvertices) is connected. Such an enumeration clearly exists; for example, one could first list the edges of T^{∗} using any enumeration, and then assemble T^{∗}, starting from the root, by adding at each of ω steps the minimal edge from the list that keeps the covered portion of T^{∗} connected. The nth edge e on the list will then be added after no more than k(n) steps, where k(n) is the sum of the list positions of all the edges on the path P in T^{∗} from the root to the far endvertex of e (induction on the length of P).

We shall use this standard construction of T^{∗} in the proof of Lemma 4.2 below, and again in §6. Note that, for each n, exactly one of the two endvertices of e_{n}^{∗} is in T_{n−1}^{∗}. This vertex will be denoted by x_{n}^{∗}, the other endvertex of e_{n}^{∗} by y_{n}^{∗}.

Lemma 4.2. Any coloured rooted TT_{ω} contains either a monochromatic TT_{ω} or an injectively coloured TT_{ω}, whose minimal vertex (in either case) is among its branch vertices.

Proof. Let T be a coloured TT_{ω}. Assume first that the colouring of T has the following property:

(4.3) For each vertex v ^{∈} T, the subtree T^{⩾v} uses infinitely many colours.

Following the standard construction of T^{∗}, we build up an injectively coloured TT_{ω} =: T′ ⊂ T, say with branch vertices x_{n} and y_{n} corresponding to the vertices x_{n}^{∗} and y_{n}^{∗} of T^{∗}, as follows. We start by picking any branch vertex of T as x_{1}. Later, whenever we come to choose a subdivided edge x_{n} … y_{n} of T′ corresponding to an edge e_{n}^{∗} of T^{∗}, we first select an upper neighbour v of x_{n} that does not lie in the (finite) part of T′ constructed so far. We then use (4.3) to choose y_{n} among the branch vertices of T^{⩾v} so that its colour differs from the (finitely many) colours used by branch vertices of T′ selected earlier, and let x_{n} … y_{n} be the unique x_{n}–y_{n} path in T.

Suppose now that (4.3) fails, i.e. that T has a vertex v such that T^{⩾v} uses only finitely many colours. Without loss of generality, v is a branch vertex. We may now obtain a monochromatic TT_{ω} inside T^{⩾v} by repeated application of Lemma 4.1: we just partition the colours used into two classes called ‘red’ and ‘blue’, apply the lemma and iterate. □

For a thorough study of Ramsey-type properties of T_{ω}, the reader is referred to Prömel and Voigt [ 8 ].

5. Good families

In our introductory discussion of the three countable types of forbidden subgraph in the bounded graph conjecture, the TT_{ω}, the bundle graph, and the fan graph, we noticed that the proofs of these graphs’ own unboundedness were very similar. In the case of T_{ω}, we just took any injective labelling and observed that, for any given sequence σ: ℕ → ℕ, we could easily find a ray R through T_{ω} which was not dominated by σ. Indeed, no matter how we had chosen an initial segment of R, we would have an infinite choice of labels for the next vertex of R, which could thus be chosen larger than the corresponding term in σ.

For a bundle graph or a fan graph, finding such a ray R was hardly more difficult. All we had to make sure of was that the paths P we considered for initial segments of R belonged to a certain family P: a family of paths which could, again and again, be extended to reach unused vertices of infinite degree. In the bundle graph B, P consisted of the paths from left to right; in the fan graph F, of those towards the right and down the spines of the fans.

The idea of finding such a family of paths in an unbounded graph is central to our proof of the bounded graph conjecture. Our aim in this section, essentially, is to prove that in every unbounded graph such a family of paths exists. In the next section we shall show that one can always reconstruct one of the forbidden subgraphs from the paths in that family.

Let us make precise the kind of family of paths in which we are interested, so that we can state exactly what we shall prove in this section. Let G be an arbitrary connected graph with a normal spanning tree T, and let T′ ⊂ T be the union of all normal rays in G. Call a pair (x, y) of distinct vertices of T′ good if G contains only finitely many T′–T′ paths from x to y, and bad otherwise. A non-empty family P of finite paths in G will be called a good family if it satisfies the following four conditions:

(i) for every path P ^{∈} P there exists an n ^{∈} ℕ such that P has infinitely many extensions in P of length n;

(ii) if P ^{∈} P, x, y ^{∈} V (P), and xP y is a T′–T′ path in G of length ⩾ 2 (i.e. with at least 2 edges), then (x, y) is a good pair;

(iii) every path P ^{∈} P starts at the root of T;

(iv) if P ^{∈} P and Q is an initial segment of P, then Q ^{∈} P.

Note that the essence of a good family is contained in condition (i): if we choose n minimal, then infinitely many extensions P′ ^{∈} P of P agree up to their nth (= penultimate) vertex and differ pairwise at their last vertex. Thus, if P is viewed as the beginning of a ray R being constructed to elude a given sequence σ (as in our discussion above), then the (n + 1)th vertex of this ray can be selected from an infinite choice, and therefore in such a way that its label exceeds the corresponding term in σ. (So, by condition (i) alone, the existence of a good family of paths in G implies that G is unbounded.)

Condition (ii) says, less formally, that paths of a good family leave and return to T′ only at good pairs of vertices. This assumption is also vital to our proof: it ensures that subgraphs constructable from the paths in a good family have many vertices on T′—for example, we shall see that any vertex of infinite degree has to be on T′—which will give us the amount of control over these subgraphs that we shall need.

Conditions (iii) and (iv) are normalization conditions; they are not essential, but they will make it easier to handle good families.

Recall that, if κ is a cardinal, I_{κ} denotes the disjoint union of κ rays. Let us define 𝔟 to be the least cardinal κ such that there exists a family of κ distinct ℕ → ℕ sequences which are not dominated simultaneously by any ℕ → ℕ sequence. (This cardinal 𝔟 is commonly known as the bounding number). Then, in particular, every family of fewer than 𝔟 sequences has a majorant. Note also that ω < 𝔟 ⩽ 2^{ω} by Lemma 1.1.

As is easy to check, 𝔟 is regular, i.e. 𝔟 is not the union (sum) of fewer than 𝔟 cardinals < 𝔟. Moreover, since I_{κ} contains exactly ω · κ = κ rays whenever κ is an infinite cardinal, 𝔟 is also the least cardinal such that I_{𝔟} is unbounded.

We can now state the theorem which we shall prove in this section.

Theorem 5.1. Let G be an unbounded graph with a normal spanning tree, and suppose that G contains neither an I_{𝔟} nor a bundle graph. Then there exists a good family of paths in G.

Proof. As usual, let the normal spanning tree of G be denoted by T, and the union of all normal rays in G by T′.

Let us show straight away that

(5.2)  |T′| < 𝔟 .

Since T′ is connected and 𝔟 is regular, it suffices to show that each vertex v ^{∈} T′ has degree < 𝔟 in T′. Let W be the set of upper neighbours of v in T′ and, for each w ^{∈} W, let R_{w} be any normal ray containing w. Then the tails wR_{w} for w ^{∈} W are pairwise disjoint. Since G ⊉ I_{𝔟} by assumption, this means that v has degree < 𝔟, as claimed.

The proof of the theorem is organized as follows. We begin by constructing a family P of paths in G which satisfies the four defining conditions of a good family, but which will not, a priori, be known to be non-empty. Such a family is easily obtained: we shall start with the family P_{0} of all paths in G which have any chance of eventually being in P (omitting, for example, any paths which violate condition (ii)), and then recursively discard those paths from this family which fail to meet the extendability condition (i).

The main part of the proof will be to show that P is indeed non-empty and therefore a good family. The key here will be that the recursion by which P is obtained takes fewer than 𝔟 steps. At each step α, we shall find a sequence σ_{α}: ℕ → ℕ which dominates all those rays in G whose initial segments were all in P_{0}, and for which some initial segment was discarded at step α. Then, by the definition of 𝔟, there will be a sequence σ which dominates all such rays in G simultaneously. Since G is by assumption unbounded, and therefore contains a ray R which is not dominated by σ, this means that the initial segments of such a ray R (after some normalization) are either still in P when the recursion ends, or were not all in P_{0} at the start of the recursion. In the former case P will be non-empty, as desired. In the latter case, it will turn out that R leaves and returns to T′ infinitely often at bad pairs (x, y); we shall then be able to construct a bundle graph in G along R (typically with the bundles occurring between these x and y), in contradiction to our assumptions.

Let us define P precisely. Let Q_{0} be the set of all paths P ⊂ G starting at the root of T and ending on T′ which only leave T′ at good pairs of vertices, i.e., which have the property that if xP y is a T′–T′ path in G of length ⩾ 2 then (x, y) is a good pair. Let P_{0} be the set of all initial segments of paths in Q_{0}; note that P_{0} includes Q_{0}. Then P_{0} satisfies conditions (ii), (iii) and (iv) from the definition of a good family.

We claim that |P_{0}| < 𝔟. As clearly |P_{0}| = |Q_{0}|, it suffices to show that |Q_{0}| < 𝔟. Now, each path P ^{∈} Q_{0} is determined by its (finite) sequence of vertices on T′ and the choice of its subpaths xP y for successive x, y ^{∈} V (P)∩V (T′). As |T′| < 𝔟, there are only < 𝔟 finite sequences of vertices of T′, and since each xP y has length ⩾ 2 only if (x, y) is good, the choice of subpaths xP y is finite for each pair (x, y). Hence |Q_{0}| < 𝔟, as required.

For all ordinals α > 0, let us inductively define subsets P_{α} of P_{0}, as follows. Suppose first that α is a successor, say α = β +1. If P_{β} contains a path P =: P_{β} which violates (i) in the definition of a good family (i.e., a path P such that, for each n ^{∈} ℕ, P_{β} contains only finitely many extensions of P of length n), let P_{α} be obtained from P_{β} by deleting P_{β} and all its extensions P′ ^{∈} P_{β}. If P_{β} contains no such path P, let P_{α} := P_{β}. If α is a limit, let P_{α} := ⋂_{β<α} P_{β}.

Since |P_{0}| < 𝔟, there exists an α < 𝔟 such that P_{α+1} = P_{α}; let α^{∗} be the least such α, and set P_{α^{∗}} =: P. Since each P_{α} satisfies conditions (ii), (iii) and (iv) from the definition of a good family, and since P = P_{α^{∗}} in addition satisfies condition (i), we see that P is a good family if and only if it is nonempty. To complete the proof, then, it suffices to show that if P is empty then G contains a bundle graph, contrary to our assumption.

Let us suppose that P is indeed empty. We shall first prove that G contains a ray R which leaves T′ infinitely often at bad pairs (x, y), and then use R to find a bundle graph in G.

(5.3) There exists a ray R ⊂ G which contains infinitely many T′–T′ paths xRy such that (x, y) is a bad pair of vertices.*

To prove (5.3), let us suppose for a contradiction that any ray in G leaves T′ only finitely often at bad pairs of vertices. We show that G is bounded, contrary to our assumptions.

Let f: V (G) → ℕ be an arbitrary labelling of G. We shall define sequences σ_{α}: ℕ → ℕ, one for each α < α^{∗}, whose majorant σ^{∗} will bound G. For each α < α^{∗}, let the kth term of σ_{α} be defined as

σ_{α}(k) := \{ \begin{matrix}f(x_{k}) & if k ⩽ |P_{α}| \\ max \{ f(v(P)) | P ^{∈} P_{α}\P_{α+1} and |P | = k \} & if k > |P_{α}|, \end{matrix}

where x_{k} is the kth vertex of P_{α} and v(P) is the last vertex of P. Recall that, by definition, P_{α} has only finitely many extensions P ^{∈} P_{α} of any given length; since P_{α}\P_{α+1} is precisely the set of P_{α} and all its extensions in P_{α}, the maximum used above is therefore just the maximum of a finite set. Finally, let σ^{∗} be the majorant of { σ_{α} | α < α^{∗} }; it exists, because α^{∗} < 𝔟.

To show that σ^{∗} bounds G, let R ⊂ G be any ray. By assumption, R leaves T′ only finitely often at bad pairs of vertices; let R′ be a tail of R which leaves T′ only at good pairs. (Recall that since R follows a normal ray (Lemma 3.9), it never leaves T′ altogether.) Let Q be a path in T′ from the root of T to R′, and let v be the last vertex of Q. Then the ray R′′ := QvR′ (= QvR) still leaves T′ at good pairs only, so every initial segment of R′′ is in P_{0}.

Now since P = ∅ by assumption, each initial segment of R′′ is discarded at some (non-limit) step in the recursive definition of P; let α < α^{∗} be minimal such that P_{α}\P_{α+1} contains an initial segment of R′′. Then P_{α} is itself an initial segment of R′′. Moreover, all the extensions of P_{α} in R′′ are also in P_{α} (by the minimality of α), and were hence discarded together with P_{α}. Thus, P_{α}\P_{α+1} contains every initial segment of R′′ of length k ⩾ |P_{α}|. Therefore σ_{α} dominates R′′, by definition of σ_{α}.

* As the reader may expect (and the proof of (5.3) will indeed show), the paths xRy can be chosen so as to have lengths ⩾ 2. However, this will not be needed when (5.3) is used below.

By Lemma 2.2, this implies that σ^{∗} dominates R, so σ^{∗} bounds G as claimed. As this contradicts our assumption that G is unbounded, we have thus completed the proof of (5.3).

Let R ⊂ G be a ray as in (5.3). Let (x_{1}, y_{1}), (x_{2}, y_{2}), … be an infinite sequence of disjoint bad pairs of vertices, such that x_{i} precedes y_{i} on R for each i and y_{i} precedes x_{j} on R for i < j. For each i, let H_{i} be the union of all T′–T′ paths in G from x_{i} to y_{i}; note that, since (x_{i}, y_{i}) is bad, H_{i} is infinite. We remark that the graphs H_{i} are not necessarily disjoint, and that H_{i} may well meet R even outside the segment x_{i}Ry_{i}.

For each i, let us find a bundle B_{i} ⊂ H_{i}, say from a vertex x′_{i} to a vertex y′_{i}, together with (possibly trivial) disjoint paths C_{i} = x_{i} … x′_{i} and C′_{i} = y′_{i} … y_{i} in H_{i} which avoid the interior of B_{i}. (These paths will be called the connectors of B_{i}; Fig. 4.)

FIGURE 4. The bundles B_{i} and their connectors

To define B_{i} for a given i, recall that since G\T′ is rayless (Lemma 3.9), H_{i} too is rayless. Since H_{i} is infinite and connected, it has a vertex v of infinite degree, by König’s theorem. As H_{i} is the union of x_{i}–y_{i} paths, each of the edges e = uv incident with v is contained in such a path P (e). Now if v precedes u on P (e) for infinitely many of these edges e then, by Lemma 2.3, the union of their paths P (e) contains a v–w bundle B (for some w) on the segment vP of one of these paths P. (Lemma 2.3 does not give a fan, because H_{i} is rayless.) Put C_{i} := P v and C′_{i} := wP in this case, and let B_{i} be obtained from B by deleting those fibres which meet P v. On the other hand, if u precedes v on P (e) for infinitely many of the edges e, then the union of the corresponding paths P (e) contains a w–v bundle B (for some w) on the segment P v of one of these paths P (apply Lemma 2.3 ‘backwards’). In that case, we let C_{i} := P w and C′_{i} := vP, and let B_{i} be obtained from B by deleting those fibres which meet vP. (This construction of a bundle in a graph such as H_{i} is due to Halin [ 5 ].)

Now that we have defined an infinite sequence of bundles along our ray R, it may seem that obtaining a bundle graph from them would be only a small step away. As remarked earlier, however, the subgraphs H_{i} containing our bundles need not be disjoint. In fact, it might even happen that two of the bundles, as well as their connectors, coincide (except for the two vertices x_{i} and y_{i}).

We shall deal with this problem as follows. By Lemma 3.9, R follows some normal ray R′. A natural way to ensure that different bundles B_{i} are disjoint, therefore, is to separate them by their R′-height: if we can find an infinite subsequence i_{1}, i_{2}, … spaced out sufficiently that each B_{i_{k}} is B_{i_{j}}-clear with respect to R′ for every j < k, then these bundles B_{i_{k}} will indeed define a bundle graph along R. For this approach to work it is essential, of course, that the R′-height of each bundle B_{i_{k}} be bounded. Unfortunately, this is not necessarily the case—so let us deal with this problem first.

Suppose there are infinitely many i such that the R′-height of B_{i} is unbounded. Since (H_{i}\{ x_{i}, y_{i} })∩T′ = ∅, every fibre of B_{i} is disjoint from R′, and so the vertices of each individual fibre have constant R′-height. If the R′-height of B_{i} is unbounded, this implies that x′_{i} has a neighbourhood of unbounded R′- height, and hence that x′_{i} = x_{i} (Lemma 3.11 (i)). If this happens for infinitely many i, the corresponding vertices x_{i}—which are all distinct—form an infinite set of vertices each with a neighbourhood of unbounded R′-height. Then G contains a TK_{ω} (and hence a bundle graph) by Lemma 3.11 (ii).

We may therefore assume from now on:

(5.4) The R′-height of B_{i} is bounded for all but finitely many i.

Using R, the bundles B_{i} and their connectors C_{i} and C′_{i}, let us construct a bundle graph in G inductively, adding one bundle at a time. More formally, let us construct by induction on n a nested sequence (G_{n})_{n^{∈}ℕ} of graphs with the following properties:

(i) G_{n} is a partial bundle graph (with n bundles), on a path P_{n} which ends in a vertex t_{n} ^{∈} R;

(ii) P_{n} has a vertex s_{n} ≠ t_{n} such that all the bundles of G_{n} are between

vertices preceding s_{n} on P_{n}; (iii) s_{n}P_{n} ⊂ R, and s_{n} precedes t_{n} on R; (iv) t_{n}R is S_{n}-clear with respect to R′, where S_{n} := G_{n}\s̊_{n}P_{n}.

(See Figure 5.)

FIGURE 5. The partial bundle graph G_{n}

Condition (iv) means that every vertex on R from t_{n} onwards has R′-height strictly greater than the R′-height of any vertex in G_{n} up to s_{n}. So in particular, the R′-height of S_{n}, and hence that of G_{n} = S_{n} ∪ s_{n}Rt_{n}, is bounded:

(5.5) G_{n} has bounded R′-height.

To define G_{0}, let s_{0} be the first vertex of R, and put G_{0} := P_{0} := Rt_{0} where t_{0} ^{∈} R is chosen so that t_{0}R is { s_{0} }-clear with respect to R′; this can be done by Lemma 3.10 (which we shall use freely in our further construction). Suppose now we have defined G_{k}, for k = 0, …, n, in accordance with conditions (i)–(iv). We shall now define G_{n+1}.

By (5.4) and (5.5), choose i ^{∈} ℕ so that B_{i} has bounded R′-height and x_{i}R is G_{n}-clear with respect to R′. Note that t_{n}Rx_{i} meets G_{n} only in t_{n}: it avoids S_{n} by (iv), and it meets s_{n}Rt_{n} only in t_{n}, because s_{n} precedes t_{n} on R by (iii) and t_{n} precedes x_{i} on R by the choice of x_{i}. Note that also

H′_{i} := (C_{i} ∪ B_{i} ∪ C′_{i}) ∖ { x_{i}, y_{i} }

is G_{n}-clear with respect to R′: since each v ^{∈} H′_{i} can be connected to x_{i} by a v–T′ path, the R′-height of v is at least that of x_{i} (Lemma 3.5).

Using our assumption that B_{i} (and hence H′_{i}) has bounded R′-height, choose u ^{∈} y_{i}R so that uR is X-clear with respect to R′, where

X := G_{n} ∪ H′_{i} .

Let B′_{i} be obtained from B_{i} by removing those fibres that have a vertex on t_{n}Ru; as there are at most finitely many such fibres, B′_{i} is still a bundle. The interior of B′_{i} then avoids t_{n}Ru, and it also avoids G_{n} (because H′_{i} does, and H′_{i} contains the interior of B′_{i}).

The connectors C_{i} and C′_{i}, however, may still meet t_{n}Rx_{i} or y_{i}Ru. Let x′′_{i} be the last vertex on C_{i} that is in t_{n}Ru, and let y′′_{i} be the first vertex on C′_{i} that is in t_{n}Ru (Fig. 6). Rename x′′_{i} and y′′_{i} as a and b, where a precedes b on R, and set

U := G_{n} ∪ t_{n}Ra ∪ (x′′_{i}C_{i}x′_{i} ∪ B′_{i} ∪ y′_{i}C′_{i}y′′_{i}) ∪ bRu .

Then U is a partial bundle graph, with n + 1 bundles, whose R′-height is bounded.

In order to complete the induction step formally, set s_{n+1} := u, and choose t_{n+1} ^{∈} uR so that t_{n+1}R is U-clear with respect to R′. Note that uRt_{n+1} ∩ U = { u }, because U ⊂ X ∪ Ru and uRt_{n+1} is X-clear by the choice of u. Set G_{n+1} := U ∪ uRt_{n+1}, and let

P_{n+1} := P_{n} ∪ t_{n}Ra ∪ (x′′_{i}C_{i}x′_{i} ∪ F ∪ y′_{i}C′_{i}y′′_{i}) ∪ bRt_{n+1} ,

FIGURE 6. Disentangling R and H′_{i}

where F is some x′_{i}–y′_{i} path in B′_{i}. Then G_{n+1} is a partial bundle graph on P_{n+1}, satisfying conditions (i)–(iv) for n + 1.

The graph ⋃_{n^{∈}ℕ} G_{n}, finally, is a bundle graph as desired. This completes the proof of Theorem 5.1. □

6. Fans and bundles from a good family tree

This section is devoted to the proof of the following theorem.

Theorem 6.1. Let G be a graph with a normal spanning tree, and suppose there exists a good family of paths in G. Then G contains a TT_{ω}, a bundle graph, or a fan graph.

Proof. As before, let the normal spanning tree of G be denoted by T, and the union of all normal rays by T′. Let P be a good family of paths in G. The method of our proof is as follows.

We shall represent the structure of P by a certain tree T , which will act as something like a covering space for the paths P ^{∈} P in G. Thus, the paths of P will ‘lift’ to paths in T , which will be arranged in such a way as to reflect the relation of extension between their projections in P.

Our main task will be to study the relationship between T and G. If G (more precisely, the subgraph ⋃ P of G) resembles T closely, we shall try to find a tree of type TT_{ω} in G. On the other hand, if the paths of P intersect a lot more (in G) than do their lifts in T , we shall seek to construct a bundle graph or a fan graph in G. The distinction between the latter two cases will depend on the relationship between T and our normal spanning tree T of G.

Recall that the essence of the fact that P is a good family of paths lies in its extension property, condition (i) of the definition of a good family: for each of its paths, P contains infinitely many extensions of some common length. We start by ‘pruning’ P to a subfamily containing no more paths than the extension property requires.

To be precise, let us define subsets Q_{0}, Q_{1}, … of P as follows. Pick any non-trivial path P_{0} ^{∈} P, and set Q_{0} := { P_{0} }. Having defined Q_{0}, …, Q_{n}, we want Q_{n+1} to be a set of extensions of the paths in Q_{n} just large enough to witness the fact that Q_{n} ⊂ P. For each P ^{∈} Q_{n}, take the minimal k such that P has infinitely many extensions of length k in P. Then infinitely many of these extensions agree up to their penultimate vertices: recall that P is closed under taking initial segments. We may thus choose infinitely many extensions P^{(0)}, P^{(1)}, … of P in P, each of length k, which differ only in their last vertices. Set

Q_{n+1} := { P^{(i)} | P ^{∈} Q_{n}, i ^{∈} ℕ } ,

and continue inductively. If we now let Q be the set of all initial segments of paths in ⋃_{n^{∈}ℕ} Q_{n}, we see that Q is a good family.

In structure, Q is rather similar to a TT_{ω}. Let us make this precise. Call a graph H a long-rooted TT_{ω} if H is a subdivision of a rooted tree whose root r has degree 1 and all of whose other vertices have countably infinite degree. The edge incident with r in this tree then corresponds to a path P in H, which will be called the long root of H. (Thus, P is the unique path r … x ⊂ H for which H\P x̊ ≃ TT_{ω}.) To avoid confusion, we may refer to r itself as the root vertex of H.

Now define a tree T as follows. The vertex set of T is Q itself. For P, P′ ^{∈} Q, we join P to P′ by an edge whenever P′ is an extension of P with |P′| = |P | + 1, i.e. if P may be obtained from P′ by removing its last vertex. Then T is a long-rooted TT_{ω}, whose root vertex ϕ is the trivial path consisting of the first vertex of P_{0} (which in turn is the root of T). Note that, for α, β ^{∈} V (T ), we have α ⩽_{T} β if and only if α is an initial segment of β.

Any long-rooted TT_{ω} contained in T and also rooted at ϕ will be called a good family tree. Clearly, the vertex set of such a good family tree is again a good family of paths in G. In fact, the only property of T we shall ever use is that it is a good family tree: we shall repeatedly prune T to a smaller good family tree T′, and then rename T′ as T .

For α ^{∈} V (T ), let v(α) denote the last vertex of the path α. Note that if β is another vertex of T and β <_{T} α, then the path β ⊂ G is a proper initial segment of the path α, and so v(β) ≠ v(α). Likewise, v(α) and v(β) will be distinct if the paths α and β were picked for Q at the same step n, and as extensions P^{(i)} of the same path P ^{∈} Q_{n−1}. We may therefore note the following:

(6.2) If T′ is a good family tree, and if α, β ^{∈} V (T′) are either comparable or upper neighbours of the same vertex γ ^{∈} T′, then v(α) ≠ v(β).

By virtue of (6.2), v can be interpreted as mapping increasing paths π ⊂ T to ‘real’ paths P ⊂ G. For example, if π = ξ_{0} … ξ_{n} is a ϕ–α path in T , then v(π) is the path v(ξ_{0}) … v(ξ_{n}) in G, which is none other than the path α ⊂ G itself. More generally, if π ⊂ T is an increasing path from α to β, and if v(α) =: a, then v(π) is precisely the subpath aβ of the path β ⊂ G. When T′ is any subgraph of T other than a path, we may use v(T′) informally to denote the set { v(α) | α ^{∈} T′ } ⊂ V (G).

Let T′ be a good family tree. We shall call α ^{∈} V (T′) a burst vertex of T′ if α has infinite degree. (Thus, the burst vertices of T′ are precisely its branch vertices other than ϕ when T′ is viewed as a long-rooted TT_{ω}.) When α ^{∈} T′ is a burst vertex, the burst at α in T′ is the union of all the paths α … γ ⊂ T′ such that γ is minimal among the burst vertices above α. These paths will be called the segments of the burst; the burst itself will be denoted by B_{T ′}(α). When T′ = T or the precise choice of the good family tree considered is irrelevant, we may abbreviate B_{T ′}(α) to B(α). Thus, a burst B(α) is a subdivided infinite star, contained in T and centred at α, its segments being the star’s subdivided edges.

Let us call a burst B(α) blocked by a vertex b ^{∈} G if infinitely many of its segments contain a vertex β ≠ α with v(β) = b. If B(α) is not blocked by any vertex of G, it will be called free.

Passing to a good family tree T′ ⊂ T if necessary, we may assume that the following is true for T :

(6.3) Whenever a burst B(α) is blocked, there is a vertex b_{α} ^{∈} G such that every segment π of B(α) contains a (unique) vertex β_{π} ≠ α with v(β_{π}) = b_{α}.

Moreover, since any segment of a burst B_{T ′}(α) in a good family tree T′ contains a segment of B_{T} (α), we see that (6.3) is in fact true for all good family trees. (Recall that any good family tree is a subtree of T .)

Let α_{0} be the lowest burst vertex in T . Then ⌊α_{0}⌋ is the long root of T , and T^{⩾α_{0}} ≃ TT_{ω}. Applying Lemma 4.1 to T^{⩾α_{0}}, we see that either there is a burst vertex α ^{∈} T such that all bursts at vertices in T^{≥α} =: T̃ are free, or T^{⩾α_{0}} has a subtree T̃ ≃ TT_{ω} (whose minimal vertex is a branch vertex) such that for every branch vertex α of T̃ the burst B_{T} (α) is blocked. In either case, let T′ be obtained from T̃ by adding the ϕ–T̃ path in T as a long root. Then T′ is a good family tree. Moreover, in the first case every burst in T′ is free, while in the second case (6.3) implies that every burst in T′ is blocked. Hence, passing to this good family tree T′, we may assume that either all bursts in T are blocked or all bursts in T are free.

Let us quickly dispose of the case when all bursts are free, by showing how to find a TT_{ω} in G. If all the bursts in T are free then, for every finite set F ⊂ V (G) and every burst vertex α, there is a segment of B(α) such that for every vertex β ≠ α on this segment we have v(β) ^{∉} F. Using (6.2), and following the method of the proof of Lemma 4.2, we may thus construct a good family tree T′ ⊂ T on which the function v is injective. (Choose segments π = α … γ inductively as in the standard construction of T^{∗} ≃ T_{ω}, in such a way that v(α̊π) is disjoint from v(π′) for the—finitely many—segments π′ chosen earlier.) The image of T′ under v then spans a long-rooted TT_{ω} in G.

We may therefore assume from now on that all bursts in T are blocked. By (6.3), this assumption carries over to all good family trees:

(6.4) If T′ is a good family tree and α is a burst vertex of T′, then B_{T ′}(α) is blocked by the vertex b_{α} ^{∈} G.

Let us continue our investigation of the bursts in good family trees. We claim the following:

(6.5) If α is a burst vertex in a good family tree T′, then v(α) ^{∈} T′.

Indeed, suppose that v(α) /^{∈} T′. Let β be the highest vertex of T′ below α such that v(β) ^{∈} T′; β exists, because v(ϕ) ^{∈} T′. Let π_{0}, π_{1}, … be the segments of B_{T ′}(α), and for each n ^{∈} ℕ let ρ_{n} be a ray in T′ which starts at β and contains π_{n}. Since these rays are increasing in T′, they correspond to rays v(ρ_{n}) =: R_{n} in G (recall the remark following (6.2)). Each of the rays R_{n} starts at v(β); let t_{n} = v(τ_{n}) be its first inner vertex on T′. This vertex t_{n} exists by Lemma 3.9, and it comes after v(α) on R_{n} by the choice of β. Moreover, the vertices t_{n} are all in T′ [ v(α) ], which is finite by Lemma 3.4. Therefore infinitely many of the t_{n} are the same (t, say), and the corresponding paths P_{n} := R_{n}t form an infinite family of T′–T′ paths in G from v(β) to t. The paths P_{n} are distinct, because v is injective on the set of upper neighbours of α in T′. Therefore (v(β), t) is a bad pair. Since P_{n} is a subpath of the path τ_{n} ^{∈} V (T′) (for any n), this contradicts the fact that V (T′) is a good family of paths in G. This completes the proof of (6.5).

Let α ^{∈} T be a burst vertex. Let us show that v(α̊πβ̊_{π}) ∩ T′ ≠ ∅ for all but finitely many exceptional segments π of B(α). In other words: for almost every segment of B(α) the corresponding path in G meets T′ before it hits the blocking vertex b_{α}.

Suppose, for a contradiction, that B(α) has infinitely many segments π_{0}, π_{1}, … such that v(α̊π_{n}β̊_{π_{n}}) ∩ T′ = ∅ for every n. We argue as in the proof of (6.5). For each n, let P_{n} := v(π_{n}), and let t_{n} be the first vertex on b_{α}P_{n} that is in T′; such a vertex exists, because the last vertex of P_{n} corresponds to another burst vertex of T , and is therefore in T′ by (6.5). Since each of the vertices t_{n} is in T′ [ b_{α}], which is finite, infinitely many of them are the same: t, say. The corresponding paths P_{n}t are therefore T′–T′ paths in G from v(α) to t; they are distinct, because the upper neighbours of α in T have distinct images under v. Hence (v(α), t) is a bad pair, a contradiction.

For every burst vertex α, let us remove from T the finitely many exceptional segments of B(α) (and all the vertices above these segments). So, by passing to a good family tree T′ ⊂ T if necessary, we may assume that, for every burst vertex α ^{∈} T and every segment π of B(α), the corresponding path v(π) ⊂ G meets T′ before it hits the blocking vertex b_{α}. Again, this carries over to all good family trees:

(6.6) If α is a burst vertex in a good family tree T′, and if π is a segment of B_{T ′}(α), then v(α̊πβ̊_{π}) ∩ T′ ≠ ∅. The first vertex τ of α̊πβ̊_{π} with v(τ) ^{∈} T′ will be denoted by τ_{π}, and we write t_{π} for v(τ_{π}).

When R is a normal ray, let us extend the definition of R-height—and the notion of ‘(·)-clear’ associated with it—from V (G) to V (T ) in the natural way, setting ht(α; R) := ht(v(α); R).

Let α be a burst vertex in some good family tree. We shall call its burst B(α) in this tree a long burst if there exists a normal ray R ⊂ G such that the neighbourhood of α in B(α) has unbounded R-height. Otherwise, B(α) is a short burst.

For each burst vertex α ^{∈} T where B(α) is a long burst, let us pick a normal ray R_{α} ⊂ G such that the neighbourhood of α in B(α) has unbounded R_{α}-height. We may then select infinitely many segments of B(α) so that the neighbours of α on these segments have distinct R_{α}-heights. The R_{α}-height on the set of these neighbours then tends to infinity. Passing to a good family tree T′ ⊂ T if necessary, we may therefore assume that, for each burst vertex α ^{∈} T with B(α) long, the R_{α}-height of its neighbours in B(α) tends to infinity.

The same is true then for every infinite subset of the set of upper neighbours of α in T . Our assumption therefore extends to all good family trees:

(6.7) Whenever B(α) is a long burst in some good family tree, the R_{α}-height of the neighbours of α in B(α) tends to infinity.

As earlier when we considered free versus blocked bursts, let us apply Lemma 4.1 to the tree T^{⩾α_{0}} ≃ TT_{ω}, where α_{0} is the lowest burst vertex in T . The lemma now implies that either there is a burst vertex α ^{∈} T such that all bursts at vertices in T^{≥α} =: T̃ are short, or else T^{⩾α_{0}} has a subtree T̃ ≃ TT_{ω} (whose minimal vertex is a branch vertex) such that for every branch vertex α of T̃ the burst B_{T} (α) is long. Let T′ be obtained from T̃ by adding the ϕ–T̃ path in T as a long root. Then T′ is a good family tree. Moreover, in the first case every burst in T′ is short, while in the second case (6.7) (applied to T ) implies that every burst in T′ is long. Passing to this good family tree T′, we may thus assume that either all bursts of T are short or all bursts of T are long.

We shall consider these two cases separately.

Case 1: All bursts in T are short.

We shall construct a bundle graph in G by induction, adding one bundle at a time. The bundle graph will consist of the image of a ray in T , together with bundles made up from some of the bursts along the ray.

To be precise, let us construct a sequence G_{0} ⊂ G_{1} ⊂ … of subgraphs of G, and a sequence α_{0} < α_{1} < … of vertices of T , so that the following four conditions are satisfied for every n ^{∈} ℕ:

(i) G_{n} is a partial bundle graph (with n bundles) on the path α_{n} ⊂ G; (ii) α_{n} is a burst vertex of T ; (iii) the vertex v(α_{n}) has degree 1 in G_{n}; (iv) the image of V (T^{>α_{n}}) under the map v is disjoint from V (G_{n}).

Roughly speaking, condition (i) asserts that our construction has been successful so far, while conditions (ii)–(iv) will enable us to continue the construction without running into obstructions.

Note that the induction starts, with α_{0} as any burst vertex of T and G_{0} as the path α_{0} in G. Note also that once we have constructed the graphs G_{n}, their union is a bundle graph in G, as required.

Let us then turn to the induction step. Suppose we have constructed G_{0} ⊂ … ⊂ G_{n} and α_{0} < … < α_{n} in accordance with conditions (i)–(iv). Put α := α_{n} and a := v(α), and let Π be an infinite set of segments of B(α). Recall that, for each π ^{∈} Π, t_{π} = v(τ_{π}) is the first vertex of v(α̊πβ̊_{π}) in T′.

Note that the vertices t_{π} cannot be the same (say t) for infinitely many π ^{∈} Π: the pair (a, t) would then be bad, contradicting the fact that av(π)t is a T′–T′ path contained in the path τ_{π} ^{∈} V (T ) (for any π with t_{π} = t). Moreover, by Lemma 3.3 each t_{π} is comparable with a. As G has only finitely many vertices below a, it follows that a < t_{π} for all but finitely many π ^{∈} Π. Replacing Π with a suitable infinite subset if necessary, we may therefore assume the following:

(6.8) The vertices t_{π} (π ^{∈} Π) are all distinct and lie strictly above a in T′.

Let

H := ⋃_{π^{∈}Π} aT′t_{π} .

H is an infinite subtree of T′. Hence, by König’s theorem, H contains either a ray or a vertex of infinite degree. If H contains a ray, then a tail of this ray is increasing in T, and is therefore a tail of some normal ray R. By construction of H and Lemma 3.5, the vertices t_{π} have unbounded R-height. The neighbours of α in B(α) then also have unbounded R-height (again by Lemma 3.5), which contradicts the fact that B(α) is short. Hence H has a vertex z of infinite degree.

Replacing Π with a suitable infinite subset, we may assume that every t_{π} lies above z, and that ⌊t_{π}⌋ ∩ ⌊t_{π′}⌋ = ⌊z⌋ whenever π ≠ π′ (Fig. 7).

By Lemma 3.2, this implies that

(6.9) If π, π′ ^{∈} Π are distinct, then any t_{π}–t_{π′} path in G meets ⌊z⌋.

FIGURE 7. The graph H ⊂ T′

For each π ^{∈} Π, let

P_{π} := v(πβ_{π}) ;

recall that v(β_{π}) is the blocking vertex b_{α} for B(α). Then

P_{Π} := { P_{π} | π ^{∈} Π }

is an infinite set of a–b_{α} paths in G whose second vertices are distinct. By Lemma 2.3, the union ⋃ P_{Π} of these paths contains a bundle or a fan; we claim it must contain a bundle:

(6.10) ⋃ P_{Π} contains a bundle B as specified in Lemma 2.3 (i).

To prove (6.10), suppose ⋃ P_{Π} contains no such bundle. Then, by Lemma 2.3, ⋃ P_{Π} contains a fan F as specified in Lemma 2.3 (ii). We shall construct, inductively, an infinite sequence Q_{0}, Q_{1}, … of disjoint paths in F, each joining two vertices of { t_{π} | π ^{∈} Π }. (Fig. 8). This will contradict (6.9), which asserts that these vertices are pairwise separated in G by the finite subgraph ⌊z⌋.

FIGURE 8. Finding the paths Q_{0}, Q_{1}, … in F

Let k ^{∈} ℕ and assume that Q_{i} has been chosen, for every i < k, so that a /^{∈} Q_{i}. Let ℓ ^{∈} ℕ be large enough that none of the paths Q_{i} meets v_{ℓ}R or any of the spokes S_{n} with n > ℓ. By Lemma 3.9, v_{ℓ}R has a vertex t on T′. Let m be such that t ^{∈} v_{m−1}Rv_{m}. By the choice of F (see Lemma 2.3), the path S_{m}v_{m}Rv_{m−1} is an initial segment of a path P_{π} ^{∈} P_{Π}. Since t_{π} is the first vertex of åP_{π} in T′, it precedes t on P_{π} or coincides with it, and is therefore itself on the path S_{m}v_{m}Rv_{m−1}. Now pick t′ ^{∈} v̊_{m}R ∩ T′, say between v_{n−1} and v_{n} on R, find π′ ^{∈} Π such that S_{n}v_{n}Rv_{n−1} is an initial segment of P_{π′}, and note that t_{π′} ^{∈} S_{n}v_{n}Rv_{n−1}. Let Q_{k} be the t_{π}–t_{π′} path in S_{m} ∪ v_{m−1}Rv_{n} ∪ S_{n}. Then a /^{∈} Q_{k}, and Q_{k} ∩ Q_{i} = ∅ for all i < k. This completes the induction step, and hence the proof of (6.10).

Note that, according to its specification by Lemma 2.3 (i), the bundle B in (6.10) is an a–x bundle on a path P ^{∈} P_{Π}, where x is some vertex of P. Moreover, each of the a–x paths in B is an initial segment of some path P_{π} ^{∈} P_{Π}; let F_{π} ⊂ P_{π} be the corresponding fibre of B.

Our aim is to obtain our new partial bundle graph G_{n+1} by adding the bundle B on to G_{n}. To ensure that G_{n+1} will be compatible with the disjointness condition (iv), however (for some suitable α_{n+1} ^{∈} T ), we first have to delete some fibres from B.

We first wish to delete those fibres F_{π} from B which do not contain t_{π}. Before we do this, we have to check that only finitely many fibres of B will be affected, i.e. that t_{π} ^{∈} F_{π} for all but finitely many of the fibres F_{π}. If this is not the case, then F_{π} ⊂ G\T′ for infinitely many π ^{∈} Π (by definition of the vertices t_{π}; recall that F_{π} is an initial segment of åP_{π}). Then t_{π} ^{∈} T′ [ x] for all these π, and hence t_{π} ^{∈} ⌊x⌋ by Lemma 3.4. Since ⌊x⌋ is finite, this means that the vertices t_{π} coincide for infinitely many of the fibres F_{π}, contradicting (6.8).

So, removing finitely many fibres from B if necessary, we may assume that t_{π} ^{∈} F_{π} for each fibre F_{π} of B. Again removing finitely many fibres, we may assume that no fibre of B meets ⌊z⌋. Hence, (6.9) implies the following:

(6.11) The fibres of B are pairwise separated by ⌊z⌋ in G.

(In particular, x ^{∈} ⌊z⌋.)

We are now almost ready to attach the bundle B to our partial bundle graph G_{n}. Choose β ^{∈} B(α) so that v(β) = x and the path αT β has length at least 2. Among all γ ⩾ β, choose one with |γ ∩ ⌊z⌋| maximal, and pick a burst vertex α_{n+1} > γ. By the choice of γ, we have

(6.12)  v(T^{≥α_{n+1}}) ∩ ⌊z⌋ = ∅.

Indeed, if δ ^{∈} T^{≥α_{n+1}} (and thus δ > γ), then the path δ ⊂ G is a proper extension of the path γ. The choice of γ implies that δ ∩ ⌊z⌋ ⊂ γ; in particular, v(δ) (which is the last vertex of δ) is not in ⌊z⌋.

As G [ v(T^{≥α_{n+1}}) ] is connected, (6.11) and (6.12) imply that at most one fibre of B contains a vertex in v(T^{≥α_{n+1}}); delete any such fibre from B. Moreover, only finitely many fibres of B can have a vertex on the (finite) path α_{n+1}\α_{n} (= v(α̊_{n}T α_{n+1})); delete those fibres as well. We may now set

G_{n+1} := G_{n} ∪ α_{n+1} ∪ B .

Let us quickly verify the induction hypothesis for n + 1. We certainly have G_{n} ⊂ G_{n+1}, and α_{n+1} is a burst vertex of T (assertion (ii)) strictly above α_{n}.

For assertion (i), recall first that α_{n+1} is an extension of the path α_{n}, and that α_{n+1}\α_{n} ∩ G_{n} = ∅ by condition (iv) for n, because V (α_{n+1}\α_{n}) ⊂ v(T^{>α_{n}}). Hence, G_{n} is a partial bundle graph on α_{n+1}. The interior of the new bundle B is contained in the union of the paths v(π̊), where π ranges over the segments of the burst B(α) = B(α_{n}). The interior of B is therefore again disjoint from G_{n} by condition (iv) for n. As the interior of B also avoids the path α_{n+1}\α_{n} (by construction; recall the deletion of fibres just before the definition of G_{n+1}), B is also a bundle on the path α_{n+1}. Finally, if B′ is any of the bundles of G_{n}, then both vertices of B′ ∩ α_{n+1} precede v(α_{n}) (= a) on α_{n+1} by condition (iii) for n, and hence they also precede the two vertices of B ∩ α_{n+1}. Hence G_{n+1} is a partial bundle graph, with n + 1 bundles, on the path α_{n+1} ⊂ G.

By the choice of α_{n+1} as strictly above β, we know that v(α_{n+1}) has degree 1 in G_{n+1} (assertion (iii)).

For assertion (iv), note that v(T^{>α_{n+1}}) is disjoint from V (G_{n}) by condition (iv) for n, since α_{n+1} > α_{n} and hence T^{>α_{n+1}} ⊂ T^{>α_{n}}. It is certainly disjoint from V (α_{n+1}) = v(ϕT α_{n+1}), and it is finally disjoint from the interior of B, since we deleted the one fibre of B that could possibly meet v(T^{≥α_{n+1}}). Hence, v(T^{>α_{n+1}}) is disjoint from V (G_{n+1}).

This completes the induction step in our construction of a bundle graph in G, and so completes Case 1.

Case 2: All bursts of T are long.

Recall that, by (6.7), each burst vertex α ^{∈} T is associated with a normal ray R_{α}, so that the R_{α}-height of the neighbours of α in B(α) tends to infinity. Let again α_{0} be the lowest burst vertex in T . Applying Lemma 4.2 to T^{⩾α_{0}}, we see that T contains a good family tree T′ with the property that the rays R_{α} are either all the same or all distinct for the burst vertices α ^{∈} T′. Let us rename T′ as T , and address the two cases in turn.

If all the rays R_{α} are the same, say R, choose a sequence of burst vertices α_{0} < α_{1} < … in T . Then v(α_{0}), v(α_{1}), … are distinct vertices of G, whose neighbourhoods have unbounded R-height. By Lemma 3.11 (ii), this implies that G contains a TK_{ω}, and hence a TT_{ω}.

We may therefore assume from now on that the rays R_{α} are all distinct:

(6.12) If α and α′ are distinct burst vertices of T , then R_{α} and R_{α′} are distinct normal rays in G.

Similarly to our construction of a bundle graph in the short burst case, we shall now construct a fan graph in G along the image of a ray from T . The construction will be more complicated, however: the individual fans will be made not just from bursts B(α) along that ray, but partly also from the rays R_{α} corresponding to these bursts.

To be precise, let us construct a sequence G_{0} ⊂ G_{1} ⊂ … of subgraphs of G, and a sequence β_{0} < β_{1} < … of vertices of T , so that the following three conditions are satisfied for every n ^{∈} ℕ:

(i) G_{n} is a partial fan graph (with n fans) on the path β_{n} ⊂ G; (ii) for every burst vertex γ > β_{n} of T , the R_{γ}-height of G_{n} is bounded; (iii) there is a burst vertex ν_{n} > β_{n} such that the image of V (β̊_{n}T ν_{n} ∪ T^{>ν_{n}})

under the map v is disjoint from V (G_{n}).

Again, roughly speaking, condition (i) asserts that our construction has been successful so far, while conditions (ii) and (iii) will enable us to continue the construction.

We apply induction on n. Taking G_{0} := β_{0} := ϕ, and letting ν_{0} be any burst vertex of T , we see that the induction starts. Note also that once we have constructed the graphs G_{n} for all n ^{∈} ℕ, their union is a fan graph in G, as desired.

Let us then turn to the induction step. Suppose we have constructed subgraphs G_{0} ⊂ … ⊂ G_{n} of G and found vertices β_{0} < … < β_{n} and ν_{n} of T in accordance with conditions (i)–(iii). In order to define G_{n+1}, we wish to construct a new fan to add to G_{n}. However, it turns out to be difficult to pinpoint directly a fan that misses the whole of G_{n}, and which can be added to G_{n} in a manner that allows the induction to continue. We shall instead define two fans (to be called F and F′), and our aim will be to show that at least one of these fans is suitable for attachment to G_{n}.

Put α := ν_{n} and R := R_{α}, and let a := v(α). As the path α ⊂ G is finite, condition (ii) implies that the R-height of G_{n} ∪ α is bounded. We may therefore choose a neighbour δ = δ_{0} of α in B(α) that is (G_{n} ∪ α)-clear with respect to R (cf. (6.7)). Let r_{0} ^{∈} R be the R-height of δ. Let us further choose segments π_{1}, π_{2}, … of B(α) such that, writing δ_{i} for the neighbour of α on π_{i} and r_{i} for the R-height of δ_{i}, we have r_{0} < r_{1} < r_{2} < . . .. For each i ^{∈} ℕ, denote v(δ_{i}) by d_{i}, and let P_{i} be a d_{i}–R path in G that ends in r_{i} (using the definition of R-height). See Figure 9.

Since P_{i}r̊_{i} ∩ R = ∅, Lemma 3.5 implies that the R-height is constant on P_{i}r̊_{i}, and thus equal to the R-height of d_{i}. Hence we have:

(6.13) For each i ^{∈} ℕ, every vertex of P_{i} has R-height r_{i}.

FIGURE 9. Constructing a fan from B(α) and R_{α}

Define a fan F from a to d := d_{0}, as follows. The spine of F is the ray P_{0}r_{0}R. Its spokes are the paths ad_{i}P_{i} for i > 0. (In other words, the ith spoke consists of the edge ad_{i} followed by the path P_{i}.) By (6.13), the spokes of F are pairwise disjoint (except for a) and avoid P_{0}, so F is indeed a fan. As further consequences of (6.13), we have the following:

(6.14) The interior of F is (G_{n} ∪ α)-clear with respect to R.

(6.15) The R-height of F tends to infinity.

In order to define our second fan F′, choose a burst vertex α′ > δ, let R′ := R_{α′}, and put a′ := v(α′). By condition (ii), the R′-height of G_{n} ∪ α′ is bounded. Moreover, since R′ ≠ R, Lemma 3.8 and (6.15) tell us that the R′-height of F is bounded. Choose a neighbour δ′ = δ′_{0} of α′ in B(α′) that is (G_{n} ∪ F ∪ α′)-clear with respect to R′. Put d′ := v(δ′), and define π′_{i}, δ′_{i}, r′_{i}, d′_{i}, P′_{i} and a fan F′ from a′ to d′ exactly as above (Fig. 10).

Statements 6.13–6.15 then have the following equivalents for F′:

(6.13′) For each i ^{∈} ℕ, every vertex of P′_{i} has R′-height r′_{i}.

(6.14′) The interior of F′ is (G_{n} ∪ F ∪ α′)-clear with respect to R′.

(6.15′) The R′-height of F′ tends to infinity.

Setting z := max (R ∩ R′), we see by (6.15) and Lemma 3.7 that there are vertices in F with R′-height z. The R′-height of δ′, and hence of every vertex in F′, is therefore greater than z:

(6.16) F′ is ⌊z⌋-clear with respect to R′.

FIGURE 10. The fans F and F′

Now let U := { x ^{∈} F | ht(x; R) ⩽ z }, and put W := U ∪ ⌊z⌋. Note that U, and hence W, is finite by (6.15). We claim that

(6.17) W separates F from F′ in G.

Indeed, consider F′ and F \W. Each vertex of F′ has R′-height greater than z, while each vertex of F \W has R-height greater than z. By Lemma 3.6, this implies that ⌊z⌋ separates F′ from F \W in G, so W separates F from F′ as claimed.

Among all γ ⩾ δ′, choose one with |V (γ) ∩ W | maximal, and pick a burst vertex ν > γ. By the choice of γ, we have v(T^{≥ν}) ∩ W = ∅. Since G [ v(T^{≥ν}) ] is connected, this implies that v(T^{≥ν}) meets at most one of F and F′. Let F′′ ^{∈} { F, F′ } be such that v(T^{≥ν}) ∩ V (F′′) = ∅, and define α′′, R′′, a′′, δ′′, d′′, r′′_{i} and P′′_{i} accordingly. Thus,

(6.18) F′′ is a fan from a′′ to d′′ which avoids v(T^{≥ν}).

Moreover, statements 6.13–6.15 and their analogues for F′ imply the following:

(6.13′′) For each i ^{∈} ℕ, every vertex of P′′_{i} has R′′-height r′′_{i}.

(6.14′′) The interior of F′′ is (G_{n} ∪ α′′)-clear with respect to R′′.

(6.15′′) The R′′-height of F′′ tends to infinity.

Our final task now is to attach this new fan to G_{n}. Set

X := { v(β) | δ′′ ⩽ β ⩽ ν } ∩ V (F′′) .

Note that X ≠ ∅, as d′′ ^{∈} X. Let Y ⊂ X consist of the vertices in X of maximal R′′-height. Pick a vertex b ^{∈} Y as follows. If Y contains a vertex on R′′, let b be this (unique) vertex. If Y ∩ V (R′′) = ∅, then all the vertices of Y lie on a common spoke of F′′ or on P′′_{0} (by (6.13′′)); let b be the vertex of Y closest to R′′ along this spoke (respectively, along P′′_{0}).

Define a fan E from a′′ to b as follows. Let r be the R′′-height of b. As the spokes of E, take those spokes of F′′ whose last vertex is above r. If b ^{∈} R′′ (and r = b), take bR′′ as the spine of E. If b /^{∈} R′′, say b ^{∈} P′′_{k}, let the spine of E be the ray bP′′_{k}rR′′. In either case, E is a fan from a′′ to b contained in F′′ (Fig 11).

FIGURE 11. The fan E ⊂ F′′

Set ν_{n+1} := ν, and let β_{n+1} be the unique vertex β ⩽ ν with v(β) = b. Note that, in fact, δ′′ ⩽ β < ν by (6.18) and the definition of X, so

α′′ < δ′′ ⩽ β_{n+1} < ν_{n+1} .

Finally, let

G_{n+1} := G_{n} ∪ β_{n+1} ∪ E .

Let us verify the induction hypothesis for n + 1. We certainly have G_{n} ⊂ G_{n+1} and β_{n} < β_{n+1}.

For assertion (i), note first that the path β_{n+1}\β_{n} = v(β̊_{n}T β_{n+1}) avoids G_{n} by condition (iii) for n. The interior of E avoids G_{n} ∪ α′′ by (6.14′′) (since E ⊂ F′′), and it avoids the path ν_{n+1}\α′′ by the choice of b. (Recall that δ′′ is an upper neighbour of α′′ in T .) In particular, E is a fan on β_{n+1}\β_{n} (recall that β_{n} < α ⩽ α′′), and (i) follows.

For a proof of assertion (ii), let γ be any burst vertex above β_{n+1}. Then γ ≠ α′′, so the R_{γ}-height of E is bounded by (6.15′′) and Lemma 3.8. As the path β_{n+1} is finite, this implies that (ii) carries over from n to n + 1.

To verify (iii), note that G_{n} avoids the set

V := v(β̊_{n+1}T ν_{n+1} ∪ T^{>ν_{n+1}})

by condition (iii) for n, because ν_{n+1} > ν_{n}. We saw in the proof of (i) that the interior of E avoids the path ν_{n+1}\α′′, so E avoids V by (6.18). The path β_{n+1} avoids V by (6.2). Hence G_{n+1} avoids V.

This completes the induction step in our construction of a fan graph in G, and so completes Case 2. The proof of Theorem 6.1 is thus complete. □

7. The bounded graph theorem

To conclude the paper, let us restate our principal result and complete its formal proof. Recall that 𝔟 denotes the least cardinal such that there exists a family of 𝔟 distinct ℕ → ℕ sequences which are not dominated by a common ℕ → ℕ sequence. (So, ω < 𝔟 ⩽ 2^{ω}, and ω_{1} = 𝔟 = 2^{ω} with CH.) Recall further that I_{𝔟} denotes the disjoint union of 𝔟 rays, and that T_{ω} is the tree of countably infinite regular degree. As in the Introduction, let B and F be the prototype bundle graph and the prototype fan graph, respectively (see Figs. 1 and 2).

Theorem 7.1. (Bounded graph theorem) A graph is bounded if and only if it contains none of the following graphs as a topological subgraph: I_{𝔟}; T_{ω}; B; F.

Proof. Since boundedness is closed under taking subgraphs, the ‘only if’ part follows from the fact that the four forbidden graphs and their subdivisions are themselves unbounded.

For the ‘if’ part, let us suppose that a graph G contains no subdivision of any of I_{𝔟}, T_{ω}, B or F; we show that G is bounded. Since G ⊉ I_{𝔟}, fewer than 𝔟 of its components contain a ray. By definition of 𝔟, we may therefore assume that G is connected. Since G does not contain a TK_{ω} (which would contain a TT_{ω}), G has a normal spanning tree by Halin’s theorem (3.1). By Theorem 6.1, then, there is no good family of paths in G, so G is bounded by Theorem 5.1. □

Remark. If the Continuum Hypothesis is assumed then ω_{1} = 𝔟 = 2^{ω}, so Theorem 7.1 implies the bounded graph conjecture as stated in the Introduction.

In the remainder of this section we list a few immediate consequences of the bounded graph theorem. The following three corollaries were already discussed in the Introduction.

Corollary 7.2. Subdivisions of bounded graphs are bounded, and subdivisions of unbounded graphs are unbounded. □

Corollary 7.3. Let G be a graph. Unless G contains 𝔟 disjoint rays (in which case it is trivially unbounded), G is bounded if and only if all its countable subgraphs are bounded. □

Corollary 7.4. If a countable graph admits some unbounded labelling then all its injective labellings are unbounded. □

Our next corollary is a strengthening of Theorem 5.1. Let us call a nonempty family P of finite paths propagating if it satisfies condition (i) of the definition of a good family, i.e., if for every path P ^{∈} P there exists an n ^{∈} ℕ such that P has infinitely many extensions in P of length n. Clearly, any graph with a propagating family of paths must be unbounded, and any graph containing a subdivision of T_{ω}, B or F contains a propagating family of paths.

Corollary 7.5. A graph G not containing I_{𝔟} is bounded if and only if there is no propagating family of paths in G. □

One may ask whether or not boundedness can also be characterized by the exclusion of minors rather than topological subgraphs. Since the minor relation is transitive, this would require that boundedness be closed under taking minors, i.e. that minors of bounded graphs should again be bounded. With the most general definition of an infinite minor, as given in §2, this is easily seen to be false: the infinite grid, for example, is locally finite and hence bounded, but contracting every second vertical ray yields a graph which contains both a copy of F and a bundle graph (and is therefore unbounded).

However, a slightly less general definition of an infinite minor (which still generalizes the usual finite definition) will work: if we require that all the branch sets be finite—i.e., if all our minors are obtained by first taking a subgraph and then contracting finite connected parts of that subgraph—then boundedness does turn out to be closed under taking minors. Indeed, if H is a bounded graph and H ⊇ H′ = HG with all branch sets finite, it is not difficult to see that any TB, TF, TT_{ω} or I_{𝔟} subgraph of G could be lifted to a corresponding TB, TF, TT_{ω} or I_{𝔟} subgraph of H′, and hence of H, contradicting the boundedness of H. Therefore G, too, must be bounded:

Corollary 7.6. Boundedness is closed under taking minors with finite branch sets. □

By Lemma 2.1, we thus have the following forbidden minor version of Theorem 7.1:

Theorem 7.7. A graph is bounded if and only if it contains none of the following graphs as a minor (with all branch sets finite): I_{𝔟}; T_{ω}; B; F. □

References

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

[2] R. Diestel, On spanning trees and k-connectedness in infinite graphs, J. Combin. Theory B (to appear).

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

[4] R. Halin, Some problems and results in infinite graphs, in: (L.D. Andersen et al., Eds.) Graph Theory in Memory of G. A. Dirac (Annals of Discrete Mathematics 41), North-Holland Publ. Co., Amsterdam/London 1989.

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

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

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

[8] H. J. Prömel and B. Voigt, Aspects of Ramsey Theory, Springer Verlag, in preparation.

[9] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340.

Reinhard Diestel Faculty of Mathematics (SFB 343) Bielefeld University D-4800 Bielefeld Germany Imre Leader Department of Pure Mathematics 16 Mill Lane Cambridge CB2 1SB England