Normal tree orders for infinite graphs

J.-M. Brochet and R. Diestel

A well-founded tree T defined on the vertex set of a graph G is called normal if the endvertices of any edge of G are comparable in T. We study how normal trees can be used to describe the structure of infinite graphs. In particular, we extend Jung’s classical existence theorem for trees of height ω to trees of arbitrary height. Applications include a structure theorem for graphs without large complete topological minors. A number of open problems are suggested.

1. Introduction: normal spanning trees

The aim of this paper is to see how a classical and powerful structural device for the study of countable graphs, the notion of a normal spanning tree, can be made available more generally. The existence of such spanning trees, while trivial in the finite case (where they are better known as depth-first search trees), is in general limited to countable graphs. By generalizing the graph theoretical trees involved to order theoretical trees, a concept better suited to express uncountably long ‘ends’, we shall be able to extend the classical existence theorems for normal trees to arbitrary cardinalities, while retaining much of their original strength.

Throughout the paper, G will denote an arbitrary connected graph. Consider a tree T ⊆ G, with a root r, say. If T spans G, the choice of r imposes a partial order on the vertex set V (G) of G: write x ⩽ y if x lies on the unique r–y path in T. T is called a normal spanning tree of G if the two endvertices of any edge of G are comparable in this order.

Normal spanning trees have proved to be a most powerful tool for the study of countable graphs; see [ 8 ]–[ 10 ] for recent examples. Naturally, it is difficult to pin this strength down to a few particular properties. All the same, there are some basic facts on which most specific applications rely.

The most fundamental of these is the fact that any two vertices are separated in G by the down-closure of their infimum in the normal spanning tree. More precisely, if T is a normal spanning tree of G, and if ⌈x⌉ and ⌈y⌉ denote the paths in T from the root to x and to y, respectively, then

(1.1) ⌈x⌉ ∩ ⌈y⌉ separates x from y in G.

(The interesting—and non-trivial—case of this is when x and y are incomparable in T, i.e. when neither lies on the T -path from the root to the other.)

One of the most typical ‘infinite’ consequences of (1.1) is the fact that for every ray (1-way infinite path) R ⊆ G there exists a ray B ⊆ T such that R ∩ B is infinite. This is usually expressed as follows:

(1.2) Every ray of G follows a branch of T.

Together with (1.1), (1.2) implies that normal spanning trees are topologically end-faithful; see [ 7 ] for details.

If (1.1) is combined with the connecting properties of T, we obtain another useful and intuitive property: the removal of down-closures in T leaves precisely the same components in G as in T.

(1.3) For every vertex x ^{∈} G, the vertex sets of the components of G\⌈x⌉ coincide with those of the components of T \⌈x⌉.

In the next sections, when we come to generalize normal spanning trees, we shall seek to preserve the above three properties (or suitable analogues) whenever possible.

It is clear that not every connected graph can have a normal spanning tree: an uncountable complete graph, for example, has none. Jung [ 13 ] has characterized the graphs that admit a normal spanning tree, as follows. Call a set U ⊆ V (G) dispersed if any ray can be separated from it by a finite set of vertices.

Theorem 1.4. (Jung) G has a normal spanning tree if and only if V (G) is the union of countably many dispersed sets.

Corollary 1.5. Every countable connected graph has a normal spanning tree.

Corollary 1.6. If G has a normal spanning tree and H is a connected subgraph of G, then H has a normal spanning tree.

Despite obvious strengths such as the above corollaries, Jung’s characterization does not always allow one in practice to decide whether or not some particular graph has a normal spanning tree. For example, there is a result of Halin [ 11 ] that every connected graph not containing a subdivided infinite complete graph has a normal spanning tree; the proof of this theorem, based on simplicial decompositions of graphs, is fairly involved and uses only the two corollaries above, not Theorem 1.4 itself.

The paper is organized as follows. In Sections 2 and 3, we discuss various generalizations of normal spanning trees to well-founded order trees. There will be one most natural such generalization, which we shall call a well linked normal tree. Unfortunately, we shall see that an arbitrary graph need not have a well linked normal tree. In Section 3, therefore, we introduce the weaker concept of a linked tree. In Section 4, on the other hand, we prove that well linked trees do always ‘nearly’ exist: in any graph we need contract only small connected subgraphs to obtain a graph which has a well linked normal tree. This theorem, though somewhat technical at first glance, will be at the core of all our subsequent results. In Sections 5 and 6, we generalize Jung’s theorem to trees of arbitrary height. In Section 7, we prove the general existence of linked trees. Section 8 is devoted to the study of cohesive graphs: these are graphs with strong connective properties featuring in our generalization of Jung’s theorem, so this section serves to explore the statement of that theorem in more detail. Section 9 includes, as an application of our results, a structural characterization of the graphs without a complete topological minor of given regular size. We conclude in Section 10 with a list of open problems.

2. Normal trees

A partially ordered set (T, ⩽) is called a tree if all its subsets of the form ⌈t⌉ = ⌈t⌉_{T} := { t′ | t′ ⩽ t } are chains and ⌈t⌉ ∩ ⌈t′⌉ ≠ ∅ for any t, t′ ^{∈} T. T is well-founded if all these chains are well-orderings. Thus, a well-founded tree has a unique minimal element, called its root. Every graph theoretical tree with a root r is a well-founded tree in this sense if we write x ⩽ y whenever x lies on the unique r–y path in this tree. All the trees considered in this paper, except for some concluding remarks in the last section, will be well-founded.

Let T be a tree. A maximal chain in T is called a branch of T; note that every branch inherits a well-ordering from T. A final segment of a branch is a tail of this branch. The length of a branch is its order type, and the (ordinal) height of T, denoted by ht(T), is the supremum of the lengths of its branches. The height ht_{T} (t) of a vertex t ^{∈} T is the order type of ⌈t̊⌉ := ⌈t⌉\{ t }. For α < ht(T) the set T^{α} of all points of height α is called the αth level of T, and we write T^{<α} := ⋃{ T^{β} | β < α }. For t ^{∈} T, we use ⌊t⌋ = ⌊t⌋_{T} to denote the subtree { t′ | t′ ⩾ t }.

The intuitive interpretation of a tree order as expressing height will also be used informally. For example, we may say that t is above t′ if t′ < t, call ⌈X⌉ = ⌈X⌉_{T} := ⋃{ ⌈x⌉ : x ^{∈} X } the down-closure of X ⊆ T, or say that X is down-closed if X = ⌈X⌉. If t < t′, we write [ t, t′] for ⌊t⌋ ∩ ⌈t′⌉, and call this set an interval in T. If there is no point between t and t′, we call t′ a successor of t.

When κ is an infinite cardinal, we call T a κ-tree if T has height κ and |T^{<α}| < κ for every ordinal α < κ. Note that, if κ is regular, this latter condition is equivalent to saying that every level of T has size < κ. A κ-tree T is narrow if it has a (unique) branch B of length κ such that for every t ^{∈} B all but < κ points of T lie above t. This branch B will be called the central branch of T. (Of course, the existence of such a central branch implies by itself that T must be a κ-tree.)

Let T be a tree defined on the vertex set of G. We shall call T normal for G if adjacent vertices of G are comparable in T. Note that this definition is compatible with and extends Jung’s notion of normality for spanning trees. For the remainder of this section, T will be an arbitrary normal tree for G.

It is not hard to show that the fundamental separation property for Jung’s trees, (1.1), carries over:*

(2.1) If x, y ^{∈} T are incomparable, then the set ⌈x̊⌉ ∩ ⌈ẙ⌉ separates x from y in G.

Indeed, let P be an x–y path in G, and let Q = v_{1}, …, v_{n} be a minimal length subsequence of the vertices of P such that x = v_{1}, y = v_{n}, and any two consecutive vertices in Q are comparable in T. (Note that P itself has this property by normality, but Q is not required to induce a path in G.) Clearly, n ⩾ 3. By the minimality of Q, v_{1} and v_{3} are incomparable in T. Since T is a tree, this implies that v_{2} < v_{1}, v_{3}. Now if n ⩾ 4, then similarly v_{3} < v_{2}, v_{4}, with a contradiction. Hence n = 3, and v_{2} ^{∈} ⌈x̊⌉ ∩ ⌈ẙ⌉.

As a typical application of (2.1), note that if X ⊆ T is connected in G (i.e., induces a connected subgraph), then X has a unique minimal element. Thus, X is a normal tree for the subgraph it induces in G.

Let us call a well-ordered sequence R of distinct vertices of G a long ray in G if each vertex in the sequence is adjacent to a cofinal subset of the vertices preceding it. As is easily seen, this is equivalent to saying that all the intervals of R are connected in G. Note that, in particular, each successor vertex must be adjacent to its predecessor in R, so a ‘long ray’ of type ω is just an ordinary ray.

Generalizing the corresponding notion from the introduction, let us say that a long ray R follows a branch B of T if R ∩ B is cofinal in R. Then also our second property of normal spanning trees, (1.2), carries over to general normal trees:

(2.2) Every long ray in G follows a branch of T.

* Note that the proof of (2.1) does not use the well-foundedness of T.

To prove (2.2), let R be a long ray in G. Choose a cofinal subsequence S of R, selecting inductively at each step a T -minimal vertex among all those vertices not equal to or preceding (on R) any previously selected vertex. Now if x, y ^{∈} S and x precedes y on R, then G contains a y–x path P whose vertices are all in the interval [ x, y] of R. By the minimal choice of x for S, none of the vertices of P is below x in T, so by (2.1), x and y must be comparable in T. Thus all the vertices of S are pairwise comparable, and hence belong to a common branch of T.

3. Linked trees

By definition, every graph has a trivial normal tree: just well-order its vertices. Of course, this does not capture the full strength of a normal spanning tree in Jung’s sense: in addition to being normal, such a tree is also a connected subgraph, its branches are paths in the graph it spans. To adapt this to general well-founded trees, let us call a normal tree for G well linked if all its branches are long rays in G.

Unfortunately, an arbitrary connected graph need not have a well linked normal tree:

Proposition 3.1. The graph K, obtained from a complete graph on ℵ_{1} vertices by subdividing every edge once, has no well linked normal tree.

Proof. Let X ⊆ V (K) be the set of vertices of infinite degree, and S ⊆ V (K) the set of vertices of degree 2. Suppose that T is a well linked normal tree for K.* We shall prove that every branch of T is countable. As X is uncountable, there will then be incomparable vertices x, y ^{∈} X. Then the set ⌈x̊⌉ ∩ ⌈ẙ⌉, which is contained in a branch and is therefore countable, separates x from y in K (2.1). But clearly, no two vertices from X can be separated in K by a countable set, contradiction.

So let B be a branch of T. In order to prove that B is countable, we show that the subgraph H induced by its interior (those vertices of B that are neither minimal nor maximal) has maximal degree 2. As the interior of B is an interval, H is connected, and will thus be countable.

Suppose then that H has a vertex x of degree ⩾ 3. Then two of its neighbours, s and s′ say, are either both above or both below x on B. We assume that x < s < s′; the other cases are analogous. Clearly x ^{∈} X, and hence s, s′ ^{∈} S. Since s′ is an interior vertex of B and intervals of B are connected in G, s′ has an upper neighbour in B. Thus x is the only lower neighbour of s′ in B, and the interval [ s, s′] ⊆ B is disconnected in G (contradiction). □

* In fact, all we shall use about T is that its intervals are connected in K; as before, we shall not make use of the well-foundedness of T.

As our aim in this paper is to develop suitable analogues to normal spanning trees that are always available, we now introduce a weakening of the concept of well linked. At first sight, this may look a little less natural, but it does preserve some essential properties of normal spanning trees, including (1.3).

Let us call a normal tree T for G linked if the following three assertions hold for every vertex x ^{∈} G; all these assertions are easily seen to be true if T is well linked.

(L1) ⌈x⌉_{T} is connected in G;

(L2) ⌊x⌋_{T} is connected in G;

(L3) if y is a successor of x in T then xy is an edge of G.

Note that if T is linked and ht(T) ⩽ ω, then, by (L3), T defines a normal spanning tree of G in Jung’s sense. We shall see in Section 7 that every connected graph has a linked normal tree.

It is instructive to see how much linked trees retain of the defining property of ‘well linked’, i.e. the property that every chain of the form ⌈x̊⌉ has a cofinal subset of neighbours of x:

(3.2) If T satisfies (L2) for all x, then every chain of the form ⌈x̊⌉ in T has a cofinal set of vertices each adjacent to a vertex in ⌊x⌋.

Indeed, suppose that y ^{∈} ⌈x̊⌉ is above every vertex of ⌈x̊⌉ with a neighbour in ⌊x⌋. Then ⌊y⌋ is disconnected in G, since the only vertices of ⌊y⌋\⌊x⌋ that could possibly (by normality) have a neighbour in ⌊x⌋ are those below x.

Together with (2.1), (L2) implies that property (1.3) from the introduction generalizes to linked normal trees:

(3.3) If T is linked then, for any X ⊆ T, the vertex sets of the components of G\⌈X⌉ are precisely the sets of the form ⌊t⌋, where t ranges over the minimal elements of T \⌈X⌉.

Problem. Which graphs have a well linked normal tree?

4. Partition trees and expansion trees

In this section we prove that every connected graph ‘almost’ has a well linked normal tree: it always suffices to contract small connected subgraphs to ensure that the quotient graph has a well linked normal tree. Although this result will look a little technical when stated precisely, we expect that it will be at least as useful for applications as the best possible approximations to well linked trees (such as linked trees) that apply to the relevant graphs themselves. The result will also form the basis for the proof of our characterization theorem for graphs with normal trees of bounded height, the generalization of Jung’s theorem (Section 6).

Let ⋃_{t^{∈}Ṫ} V_{t} be a partition of V (G) into non-empty sets V_{t}. If the index set Ṫ of this partition is a tree, we call it a partition tree for G. For vertices v ^{∈} G, we write t(v) for the point t ^{∈} Ṫ such that v ^{∈} V_{t}. Whenever we speak of a partition tree Ṫ for G, we shall assume that it comes with a fixed partition of V (G); the sets V_{t} and the map v ↦ t(v) will then be well defined.

If Ṫ is a partition tree for G, we denote by Ġ the graph obtained from G by contracting the sets V_{t}, t ^{∈} Ṫ. We may then identify Ṫ with the vertex set of Ġ; thus, two points t, t′ ^{∈} Ṫ become adjacent vertices of Ġ if and only if G contains a V_{t}–V_{t′} edge. We shall call Ṫ a normal partition tree for G if the following two conditions are satisfied: (P1) for every t ^{∈} Ṫ, the set V_{t} is connected in G, and either |V_{t}| = cf (ht(t))

or |V_{t}| = 1; (P2) Ṫ is a well linked normal tree for Ġ.

The intuition behind the first of these requirements is simply that the partition sets V_{t} should be (connected and) ‘small’. Any reader who finds the cofinality condition uncomfortably technical will lose little by replacing it with the requirement that |V_{t}| ⩽ ht(t): the important thing is that there are no more vertices in V_{t} than there are points in Ṫ below t.

A partition tree Ṫ for G gives rise to trees on V (G) in a natural way: just replace each point t ^{∈} Ṫ with a minimal length well-ordering of V_{t}, relating vertices from distinct sets V_{t} ≠ V_{t′} as t and t′ were related in Ṫ. Such trees will be called expansions of Ṫ. Note that any expansion of a normal partition tree for G is itself normal for G (but not necessarily linked); we shall call such trees normal expansion trees for G.

Even though a normal expansion tree need not itself be well linked, it resembles closely the (well linked) normal partition tree from which it has arisen. If T is a fixed expansion of Ṫ, then every down-closed chain Ḃ in Ṫ (in particular, every branch) expands canonically to a down-closed chain B in T. Conversely, if B is a down-closed chain in T whose length is an infinite cardinal, then B is the canonical expansion of some down-closed chain in Ṫ: any partition set V_{t} is either contained in B or disjoint from it.

More generally, it is straightforward to prove the following.

(4.1) Let κ be an infinite cardinal, T an expansion of a normal partition tree Ṫ for G, Ḃ a down-closed chain in Ṫ, and B the canonical expansion of Ḃ.

(i) B has length κ if and only if Ḃ has length κ.

(ii) T has height κ if and only if Ṫ has height κ.

(iii) T is a κ-tree if and only if Ṫ is a κ-tree.

(iv) T is a narrow κ-tree if and only if Ṫ is a narrow κ-tree, and then the central branch of Ṫ expands to the central branch of T.

Thus, since the vertex sets contracted for a normal partition tree are small, the shape of such a tree does not differ much from the shape of its expansions. Together with the fact that connected subgraphs of Ġ expand to connected subgraphs of G, this will help us in subsequent sections to recover for normal expansion trees for G some of the most essential properties of well linked normal trees.

However, while G itself need not in general have a well linked normal tree, it always has a normal partition tree (and hence a normal expansion tree):

Theorem 4.2. Every connected graph has a normal partition tree.

Proof. For later use, we prove a slightly stronger (if more technical) assertion. Call a partition tree Ṫ for G adapted to a given well-ordering of V (G) if there exists a map ϕ: Ṫ → Ṫ, with image ϕ(Ṫ) =: T̈, say, satisfying the following three conditions (a)–(c):

(a) For each t ^{∈} Ṫ, ϕ(t) ⩾Ṫ t, with equality if t ^{∈} T̈.

(b) For each t ^{∈} T̈, ϕ^{−1}(t) is a finite interval in Ṫ (containing t itself as its maximal element).

For each t ^{∈} T̈, put

W_{t} := ⋃_{ϕ(t′)=t} V_{t′} .

These sets W_{t} form another partition of V (G), and each of them is an interval in any expansion T of Ṫ. Let w_{t,T} denote the T -minimal vertex in W_{t}, and let w_{t,V (G)} denote the first element of W_{t} in the well-ordering of V (G). Note that the T -order on the vertices w_{t,T} induces a tree order on the sets W_{t}, and the well-ordering on the vertices w_{t,V (G)} inherited from the well-ordering of V (G) induces a well ordering on the sets W_{t}.

(c) The well-ordering on the sets W_{t} (t ^{∈} T̈) extends their tree order.

We prove the following:

(4.3) For every well-ordering of V (G), there exists a normal partition tree for G adapted to this well-ordering.

We shall construct a partition tree Ṫ for G inductively, as the nested union of trees Ṫ_{α}, where α runs over some initial segment of the ordinals. For each α, we put

Ṫ′_{α} := ⋃_{β<α} Ṫ_{β} ,

and associate with each t ^{∈} Ṫ_{α} a set V_{t} ⊆ V (G). These sets will be disjoint for different t, so the well-orderings on each of these sets given by our well-ordering of V (G) will define expansions T_{α} of Ṫ_{α} and T′_{α} of Ṫ′_{α}. For v ^{∈} T_{α}, we write t(v) for the point t ^{∈} Ṫ_{α} with v ^{∈} V_{t}, as usual.

For each α, Ṫ_{α}\Ṫ′_{α} will consist of a single new point t_{α}; we shall abbreviate V_{t_{α}} to V_{α}. For any component C of G − T′_{α}, we set

C^{−} := { t(v) | v ^{∈} T′_{α} and v has a neighbour in C } .

(This set C^{−} will depend only on C, not on α: if β ≠ α and C is also a component of G − T′_{β}, then C will have exactly the same neighbours in T′_{β} as in T′_{α}.)

For every α, the following two conditions will be satisfied:

(i) if β < α, then Ṫ_{β} is a down-closed subtree of Ṫ_{α}; (ii) for every component C of G − T_{α} (= G − T′_{α+1}), the set C^{−} is a chain

in Ṫ_{α}. For α = 0, we set V_{0} := { x_{0} }, where x_{0} is the minimal vertex in the

well-ordering of V (G). The tree Ṫ_{0} = { t_{0} } is thus defined, and conditions (i) and (ii) hold trivially for α = 0. Now assume that for every β less than some ordinal α > 0 we have constructed a tree Ṫ_{β} so that β satisfies conditions (i) and (ii). Then Ṫ′_{α} is again a (well-founded) tree.

If T′_{α} contains all the vertices of G, we terminate the construction and set Ṫ := Ṫ′_{α}. Otherwise, we let x_{α} be the least vertex in the well-ordering of V (G) that is not in T′_{α}, and let C_{α} be the component of G − T′_{α} containing x_{α}. Then C_{α}^{−} is a chain in Ṫ′_{α}. Indeed, if α is a successor, α = β + 1 say, then Ṫ′_{α} = Ṫ_{β} and the above assertion is just (ii) for β. If α is a limit, the assertion follows easily from condition (ii) for all β < α.

If C_{α}^{−} has a maximal element t, consider the vertices v ^{∈} C_{α} with a neighbour in V_{t}. Choose one such v =: v_{α} at minimal distance from x_{α} in C_{α}, and put V_{α} := { v_{α} }. Let Ṫ_{α} be obtained from Ṫ′_{α} by placing the new point t_{α} directly above t, as its successor (and incomparable with any other point above t).

Assume now that C_{α}^{−} has no maximal element. Set κ := cf (C_{α}^{−}), and let S be a cofinal subchain of C_{α}^{−} of length κ. For each s ^{∈} S, pick a neighbour of a vertex v_{s} ^{∈} V_{s} in C_{α}, and let U be the set of all these neighbours. If |U| < κ, then U contains a vertex u adjacent to κ distinct vertices v_{s} (because κ is regular). Then { s ^{∈} S | u is adjacent to v_{s} } is cofinal in S (and hence in C_{α}^{−}), and we put V_{α} := { u }. On the other hand if |U| = κ, we let V_{α} be the vertex set of a connected subgraph of C_{α} that contains U and has size κ. In either case, we let Ṫ_{α} be obtained from Ṫ′_{α} by placing the new point t_{α} directly above C′_{α}, i.e. so that every t ^{∈} ⌈C′_{α}⌉ is below t_{α} and t_{α} is incomparable with any other point in Ṫ_{α}. It is easily checked that α satisfies conditions (i) and (ii).

It is clear from the way the sets V_{α} are defined that Ṫ is a normal partition tree for G. Furthermore, let us note the following from the construction of Ṫ. Consider any α such that x_{α} ^{∈} V_{α}; put x := x_{α}. There may be some β < α with x_{β} = x. Let β_{0} be the minimal such β. Then x_{β} = x for all β with β_{0} ⩽ β ⩽ α, i.e. x remains the ‘target vertex’ until it is eventually included in V_{α}. But the distance in C_{β} between x and v_{β} decreases at each (successor) step β, so there can be only finitely many such β. Moreover, if β′ = β + 1, then v_{β′} is adjacent to v_{β}, so t_{β′} is a successor of t_{β} in Ṫ. Thus, the points t_{β} ^{∈} Ṫ with x_{β} = x form a finite interval in Ṫ, with t_{α} at the top.

In order to prove that Ṫ is adapted to the well-ordering of V (G), define ϕ: Ṫ → Ṫ by mapping each t = t_{β} to the point t_{α} with x_{β} ^{∈} V_{α}. This satisfies (a) and (b). To verify (c), let t_{1}, t_{2} ^{∈} T̈ be given, and assume that w_{1,T} <_{T} w_{2,T}, where w_{1,T} = w_{t_{1},T} and w_{2,T} = w_{t_{2},T}. We have to show that w_{1,V (G)} := w_{t_{1},V (G)} precedes w_{2,V (G)} := w_{t_{2},V (G)} in the well-ordering of V (G). For i ^{∈} { 1, 2 }, let β_{i} be such that w_{i,T} ^{∈} V_{β_{i}}; then w_{i,V (G)} = x_{β_{i}}. Since the ‘earlier’ of the two trees T_{β_{i}} is a down-closed subtree of the other (by condition (i)), and since w_{1,T} <_{T} w_{2,T} by assumption, we have β_{1} < β_{2}. Thus x_{β_{2}} ^{∈} G − T′_{β_{1}}, and so x_{β_{2}} was a candidate for the place of x_{β_{1}}. The fact that w_{1,V (G)} = x_{β_{1}} was chosen instead shows that it precedes w_{2,V (G)} = x_{β_{2}} in the well-ordering of V (G). □

Under the aspect of ‘linkedness’, one of the strongest tangible assets of a normal expansion tree T is that the tails of its branches are almost connected in G. Indeed, let B be a branch of T, expanded from a branch Ḃ of Ṫ, say, let v ^{∈} B, and let t be the successor of t(v) on Ḃ. Then the tail of Ḃ starting at t expands to a tail of B starting ‘just above’ v, and this tail is connected in G.

Naturally, it would be interesting to know whether or not every connected graph has a normal tree for which every tail of a branch induces a connected subgraph. (Remember, this is true for well linked normal trees, where all intervals are connected.)

5. Cohesive subgraphs and dispersed sets

This section lays the foundations for our generalization of Jung’s characterization theorem (Theorem 1.4) to normal trees of arbitrarily bounded height.

The reason why it makes sense to impose a bound on the height of the normal trees we look for is that short trees tend to be more valuable than tall ones: recall the trivial observation that any graph has a normal tree of large height, given by a well-ordering of its vertices. In other words, we now seek to ensure by a global restriction on the trees’ height what the definition of ‘well linked’ aimed to ensure locally: that vertices are not placed above each other if they can be put at the same level.

Consider Jung’s theorem. In our terms, it says that G has a linked normal tree of height ⩽ ω if and only if its vertex set is the union of countably many dispersed sets. In order to adapt this theorem to trees whose height is bounded by an arbitrary cardinal κ, we first have to generalize the notion of a dispersed set.

One way of doing this would be to call a set κ-dispersed if it can be separated by fewer than κ vertices from a tail of any long ray. However, dispersion is not so much about the cofinality of rays as their connectedness, i.e. about separation not so much from a ‘tail’ of a ray as from a connected subset of it that contains almost all of its vertices. (When a ray may be longer than ω, this can make a difference, since its cofinality may still be small.) We therefore replace the rays from the countable notion of dispersed, not by long rays, but by ‘cohesive subgraphs’ defined as follows.

Definition. Let κ be an infinite cardinal. A graph H is called κ-cohesive if |H| ⩾ κ and, for every X ⊆ V (H) with |X| < κ, the graph H − X has a component containing all but < κ of the vertices of H. If H is |H|-cohesive, it is called cohesive.

Note that long rays of regular cardinal length induce cohesive subgraphs.

It is easy to see that if λ is a limit cardinal and G is κ-cohesive for every κ < λ, then G is λ-cohesive. Thus, provided that G is ℵ_{0}-cohesive, there exists a largest infinite cardinal λ such that G is κ-cohesive for all κ ⩽ λ; we may call this cardinal the cohesion of G. For example, any subdivision of a complete graph on λ vertices has cohesion λ.

Clearly, any ray is (ℵ_{0}-) cohesive. Conversely, every ℵ_{0}-cohesive graph contains a ray: this is not difficult to prove, and it will also follow instantly from Proposition 5.2 below (together with Theorem 4.2). Thus, although ℵ_{0}- cohesive subgraphs are formally more general things than rays, their presence in a given graph is equivalent to the presence of rays.

As we shall see below, if T is a normal tree for G, then any κ-cohesive subgraph of G will have almost all its vertices close to some particular branch of T. If this branch has length κ, it will be unique and thus correspond to that particular κ-cohesive subgraph. (If it is longer, its first κ points will be unique.) Now if κ is regular and T is well linked, the converse of this is true as well: since the branches of T (and their initial segments) are now long rays, the first κ points of any branch induce a κ-cohesive subgraph in G. Thus, in a well linked tree there are no ‘unnecessarily long’ branches, confirming the intuition that such trees are ‘as short as possible’.

Now consider a branch Ḃ in a normal partition tree Ṫ for G. For any regular cardinal κ, the first κ points of Ḃ induce a κ-cohesive subgraph in Ġ. Since the partition sets V_{t} ⊆ V (G) for Ṫ are small and induce connected subgraphs, these cohesion properties of Ḃ are preserved in any expansion of Ḃ. Thus, in the sense of the last paragraph, normal expansion trees for G are just as economical as well linked normal trees—their advantage being that they always exist. Here, essentially, lies the justification for our technical definition of a normal partition tree.

To make all this more precise, let T be an expansion of a normal partition tree Ṫ for G, and let Ḃ ⊆ Ṫ be a down-closed chain (i.e. the initial segment of a branch).

(5.1) If Ḃ has regular cardinal length, then the canonical expansion B ⊆ T of Ḃ induces a cohesive subgraph in G.

Indeed, let X ⊆ B be a set of size < κ := |Ḃ|. (Recall that |B| = |Ḃ| by (4.1).) As κ is regular, there exists an α < κ such that ht Ṫ (t(x)) < α for every x ^{∈} X. The final segment Ḃ′ of Ḃ starting at level α contains all but |α| < κ points of Ḃ and is connected in Ġ. Hence, the final segment B′ := { v ^{∈} B | t(v) ^{∈} Ḃ′ } of B contains all but at most |α|^{2} = |α| < κ of the points of B and is connected in G. As B′ ∩ X = ∅, this shows that B induces a cohesive subgraph in G.

For the remainder of this section, let κ be any infinite cardinal. T will be a normal tree for G, fixed until (5.6) inclusive.

The following proposition describes the shape of cohesive graphs: they have narrow normal trees. More generally, if G is κ-cohesive but possibly larger than κ, then the first κ levels of T form a narrow κ-tree:

Proposition 5.2. If G is κ-cohesive, then T^{<κ} is a narrow κ-tree.

Proof. We inductively choose a down-closed increasing sequence { x_{α} | α < κ } ⊆ T^{<κ} with the property that, for each α < κ, all but < κ points of T lie above x_{α}. It is then clear that T^{<κ} is a narrow κ-tree, with the set { x_{α} | α < κ } as its central branch.

Let α < κ be given, and assume that vertices x_{β} have been chosen correctly for all β < α. Then S := { x_{β} | β < α } is a down-closed set in T^{<κ}.

Since |S| < κ and G is κ-cohesive, G − S has a component C containing all but < κ of the vertices of G. Let x be the unique minimal element of that component (cf. (2.1)). For each β < α, all but < κ vertices of C lie above x_{β} (by our inductive assumption); let c_{β} ≠ x be such a vertex. Then x and x_{β} are both below c_{β}, and are hence comparable. Since ⌈x_{β}⌉ ⊆ S (as S is down-closed), we cannot have x < x_{β}. Thus x_{β} < x for every β < α.

To complete the induction step, let x_{α} be the minimal vertex of (⌈x⌉\S). Then x_{β} < x_{α} for every β < α (since S is down-closed), { x_{β} | β ⩽ α } is down-closed in T and hence contained in T^{<κ}, and all but < κ of the vertices of T lie above x_{α}. □

Let us note the following from the proof of Proposition 5.2:

(5.3) If G is κ-cohesive and x is a point on the central branch of T^{<κ}, then all but < κ of the vertices of G lie above x in T.

Proposition 5.2 shows that κ-cohesive subgraphs of G, like long rays, ‘follow’ branches of T. In particular:

(5.4) If H ⊆ G is κ-cohesive, then T has a branch B with |B ∩ V (H)| ⩾ κ.

Indeed, as the tree T ∩ V (H) is normal for H, it contains a narrow κ-tree. It therefore has a branch of length ⩾ κ, which lies in a branch of T.

Note that the branch B in (5.4) will be unique if it has length κ.

Based on the notion of a cohesive subgraph, we may now generalize Jung’s definition of a dispersed set.

Definition. A set U ⊆ V (G) is called κ-dispersed in G if |U ∩ V (H)| < κ for every κ-cohesive subgraph H ⊆ G.

Note that any subset of a κ-dispersed set is again κ-dispersed. Conversely, a set is κ-dispersed as soon as all its subsets of size κ are κ-dispersed. Similarly, any union of fewer than cf (κ) κ-dispersed sets is again κ-dispersed.

The property of being κ-dispersed has the following seemingly stronger equivalent:

(5.5) If U is κ-dispersed in G, then U can be separated from any κ-cohesive subgraph H ⊆ G by < κ vertices.

Indeed if U cannot be separated from H by < κ vertices, then G contains κ disjoint U–H paths (by Menger’s theorem). The union of these paths with H is a κ-cohesive subgraph containing κ vertices from U, so U cannot be κ-dispersed.

Using (5.5) and the fact that every ℵ_{0}-cohesive graph contains a ray, it is not difficult to show that our notion of ‘ℵ_{0}-dispersed’ is equivalent to the classical notion of ‘dispersed’ as defined in the introduction. Indeed, if U ⊆ V (G) can be finitely separated from any ray in G, it cannot share infinitely many vertices with an ℵ_{0}-cohesive subgraph H ⊆ G: let R ⊆ H be a ray, let S ⊆ V (G) be a finite set separating U from R, and note that (by ℵ_{0}-cohesiveness) all but finitely many vertices of H are in the component of G − S that contains a tail of R (but no vertices of U). The other direction is immediate from (5.5) and the fact that rays are cohesive.

Proposition 5.2 implies that the lower levels (and, more strongly, all short down-closed subtrees) of T are examples of κ-dispersed sets:

(5.6) Every down-closed subtree U ⊆ T that has no branch of length κ is κ-dispersed.

Indeed, let H be an arbitrary κ-cohesive subgraph of G. Then T ∩ V (H) is a normal tree for H. By Proposition 5.2, the first κ levels of this tree form a narrow κ-tree; let B be its central branch. Since B has length κ but every branch of U is shorter, B contains a point x such that U ∩ ⌊x⌋ = ∅. By (5.3), ⌊x⌋ contains all but < κ of the vertices of H, so U meets H in fewer than κ vertices.

It is easy to see that levels of T at height ⩾ κ need not be κ-dispersed.

Our next proposition, which we are able to prove only for regular κ, shows that the above examples of κ-dispersed sets are in fact canonical: any κdispersed subset of V (G) is contained in the first κ levels of some normal tree for G.

Proposition 5.7. If κ is regular and U ⊆ V (G) is κ-dispersed, then G has a normal tree T such that ⌈U⌉_{T} has no chain of length κ. In particular, U ⊆ T^{<κ}.

Proof. For later use, we prove the following more technical statement, which together with (4.3) implies the assertion.

(5.8) Whenever κ is a regular cardinal, U ⊆ V (G) is κ-dispersed, V (G) is wellordered with U as an initial segment, Ṫ is a normal partition tree for G adapted to this well-ordering, and T is any expansion of Ṫ, then ⌈U⌉_{T} has no chain of length κ.

Suppose, for a contradiction, that ⌈U⌉ ∩ T^{<κ} has a branch B of length κ. Let Ḃ := { t(v) | v ^{∈} B }; then Ḃ is a down-closed chain in Ṫ of length κ, i.e. a branch of Ṫ^{<κ}, and B is its canonical expansion.

Let ϕ: Ṫ → Ṫ be a map witnessing that Ṫ is adapted. Let T̈ and W_{t}, w_{t,T}, w_{t,V (G)} (for t ^{∈} T̈) be defined as in the definition of ‘adapted’. Note that |ϕ(Ḃ)| = |Ḃ| = κ, since inverse images under ϕ are finite. Let Ȧ := ⌈ϕ(Ḃ)⌉Ṫ; then Ȧ ⊇ Ḃ. Let A ⊇ B be the canonical expansion of Ȧ, i.e. let A := { v ^{∈} T | t(v) ^{∈} Ȧ }. Using the regularity of κ it is easy to show (as in the proof of (5.1)) that A induces a κ-cohesive subgraph in G. To obtain a contradiction, it thus suffices to prove that |U ∩ A| ⩾ κ.

We prove this by showing that w_{t,V (G)} ^{∈} U for every t ^{∈} Ȧ ∩ T̈ (= ϕ(Ḃ)); recall that there are κ such t. Let t ^{∈} Ȧ ∩ T̈ be given. Then w_{t,T} ^{∈} B ⊆ ⌈U⌉, so there exists a u ^{∈} U above w_{t,T} in T. Let t′ := ϕ(t(u)). Then w_{t,T} ⩽_{T} w_{t′,T} (with equality iff t = t′), since W_{t′} is a T -interval containing u. As Ṫ is adapted, this implies that w_{t,V (G)} precedes w_{t′,V (G)} in the well-ordering of V (G) (or w_{t,V (G)} = w_{t′,V (G)}). Since w_{t′,V (G)} in turn precedes or is equal to u (by u ^{∈} W_{t′} and the definition of w_{t′,V (G)}) and U is an initial segment of V (G), we deduce that w_{t,V (G)} ^{∈} U, as desired. □

Corollary 5.9. If κ is regular, then any κ-dispersed set U ⊆ V (G) is also λdispersed for all λ > κ.

Proof. By Proposition 5.7, we have U ⊆ T^{<κ} for some normal tree T for G. By (5.6), T^{<κ} is λ-dispersed for every cardinal λ > κ. □

Corollary 5.10. If κ is regular and G is λ-cohesive for some cardinal λ > κ, then G has a κ-cohesive subgraph.

Proof. As G is λ-cohesive, V (G) is not λ-dispersed in G. Then, by Corollary 5.9, V (G) is not κ-dispersed. Therefore G has a κ-cohesive subgraph.

□

We shall see in Section 8 that these two corollaries are in fact true for all infinite κ, regular or singular.

6. Normal trees of bounded height: a characterization theorem

We are now ready to generalize Jung’s characterization theorem to trees of arbitrary height. Most of the work needed for the regular case has been done already, so let us state this case first.

Theorem 6.1. Let κ be a regular cardinal. G has a normal tree of height at most κ if and only if V (G) is the union of at most κ κ-dispersed sets.

Proof. The forward implication is immediate from (5.6), which implies that the first κ levels of any normal tree for G are each κ-dispersed. For the converse, we once more prove a slightly stronger statement for later use (compare with Proposition 5.7):

(6.2) For κ regular, let { U_{α} | α < κ } be a family of κ-dispersed subsets of V (G), and let U denote their union. Then G has a normal expansion tree T such that U ⊆ T^{<κ}.

It is clear that (6.2) implies the original statement of the theorem: if U = V (G), then T = T^{<κ}.

For a proof of (6.2), we may clearly assume that the sets U_{α} are disjoint (though some of them may be empty). For each α < κ, set U′_{α} := ⋃_{β<α} U_{β}. Since κ is regular, each of the sets U′_{α} is again κ-dispersed.

Our well-ordering of the sets U_{α} defines a partial order on U. Extend this to a well-ordering of U, and let this well-ordering of U be an initial segment of a well-ordering of V (G). Let Ṫ be a normal partition tree for G adapted to this well-ordering, and let T be any expansion of Ṫ. By (5.8) we have U′_{α} ⊆ T^{<κ} for every α < κ, so U ⊆ T^{<κ} as desired. □

We do not know whether Theorem 6.1, as stated above, extends to singular κ. However, we have the following result for arbitrary κ, which includes Theorem 6.1 as a special case.

Let us call a subset of V (G) κ^{−}-dispersed in G if it is λ-dispersed in G for some regular λ ⩽ κ. By Corollary 5.9, any κ^{−}-dispersed set is also κ-dispersed. For regular κ, therefore, the two notions coincide.

Theorem 6.3. Let κ be any infinite cardinal. The following statements are equivalent:

(i) G has a normal tree of height ⩽ κ; (ii) V (G) is the union of at most cf (κ) κ^{−}-dispersed sets; (iii) V (G) is the union of at most κ κ^{−}-dispersed sets.

Proof. (i)→(iii) Let T be any normal tree for G of height ⩽ κ. By (5.6), each of the subtrees T^{<α} (α < κ) is |α|^{+}-dispersed, and thereby κ^{−}-dispersed.

(iii)→(ii) This is trivial when κ is regular, so let us assume that κ is singular. Choose an increasing sequence (κ_{α})_{α<cf (κ)} of regular cardinals κ_{α} < κ cofinal in κ; thus, sup κ_{α} = κ. By assumption and Corollary 5.9, V (G) is the union of at most κ sets each κ_{α}-dispersed for some α < cf (κ). We may thus write this family of sets as (U_{α}^{β})_{α<cf (κ)}^{β<κ}, where each U_{α}^{β} is κ_{α}-dispersed. (There may be some ‘dummy’ sets U_{α}^{β} = ∅.) For each α < cf (κ), let

U_{α} := ⋃_{{α′⩽α \atop β<κ_{α}}} U_{α′}^{β} .

By Corollary 5.9, and since the sequence (κ_{α})_{α<cf (κ)} is increasing, each of the sets U_{α′}^{β} is κ_{α+1}-dispersed. Hence U_{α}, the union of at most |α| · κ_{α} = κ_{α} such sets, is again κ_{α+1}-dispersed, and

V (G) = ⋃_{α<cf (κ)} U_{α} .

(ii)→(i) As in the proof of Theorem 6.1 let { U_{α} | α < cf (κ) } be a family of disjoint (but possibly empty) sets whose union is V (G), such that each set U_{α} is κ_{α}-dispersed for some regular cardinal κ_{α} < κ. For each α < cf (κ), there clearly exists a regular cardinal λ_{α} < κ such that λ_{α} ⩾ sup_{β<α} κ_{β} and λ_{α} > |α|. Then, for all β < α < cf (κ), the set U_{β} is λ_{α}-dispersed (Corollary 5.9), and so U′_{α} := ⋃_{β<α} U_{β} is λ_{α}-dispersed.

We now proceed as in the proof of Theorem 6.1. The well-ordering of the partition sets U_{α} defines a partial ordering on V (G), which we extend to a well-ordering of V (G). Let T be an expansion of a normal partition tree for G adapted to this well-ordering. Since the λ_{α} are regular, (5.8) implies that U′_{α} ⊆ T^{<λ_{α}} ⊆ T^{<κ} for each α, so T = T^{<κ}. □

It may be worth noting that, in the proof of the implication (ii)→(i) for Theorem 6.3 as in the proof of Theorem 6.1, we were free to choose the minimal vertex in the well-ordering of V (G), which became the root of the normal tree constructed.

Note also that we constructed not just any normal tree for G but a normal expansion tree. We thus have the following corollary which, given the strength of normal expansion trees, may come as a pleasant surprise:

Corollary 6.4. Let κ be any infinite cardinal. If G has a normal tree of height ⩽ κ then G has a normal expansion tree of height ⩽ κ. □

(Compare with Theorem 9.1 below.) In particular:

Corollary 6.5. G has a normal expansion tree of height ⩽ |G|.

As remarked before, any connected subgraph of a graph with a normal tree of height ⩽ κ also has such a normal tree: just take the induced partial order (cf. (2.1)). The corresponding statement for normal expansion trees seems far from obvious. However, it follows immediately from Corollary 6.4, giving us the direct analogue to Corollary 1.6:

Corollary 6.6. Let κ be any infinite cardinal. If G has a normal expansion tree of height ⩽ κ then so does every connected subgraph of G. □

Finally, one might conjecture that the graphs admitting normal trees of height ⩽ κ could also be characterized in terms of the size of their κ-cohesive subgraphs. Indeed, by Proposition 5.2, if G has a normal tree of height ⩽ κ, then any κ-cohesive subgraph of G can only have size κ; is the converse also true?

Not quite. For example, suppose that V (G) is the binary tree of height ω + 1 (i.e. the tree in which every branch has length ω + 1 and every non-maximal point has exactly two successors), and that two points t < t′ in this tree are joined by an edge if and only if t′ is maximal (i.e. has height ω). It is not difficult to show from (5.3) that every ℵ_{0}-cohesive subgraph of G must be countable. On the other hand, G has no normal tree of height ⩽ ω: since any such tree would have a point with uncountably many successors, the (finite) down-closure of this point would separate G into uncountably many components (which is impossible).

As a consequence of Theorem 9.1, however, we shall obtain the following (recall that any subdivision TK_{κ^{+}} of a complete graph on κ^{+} vertices is κcohesive):

(6.7) If all κ-cohesive subgraphs of G have size κ, then G has a normal expansion tree in which every branch has length < κ^{+}.

We do not know whether the bound of κ^{+} in (6.7) is best possible (as an ordinal bound). In other words, if all κ-cohesive subgraphs of G have size κ, does G necessarily have a normal tree (or normal expansion tree) of height < κ^{+}?

7. The existence of linked trees

The main result of this section is the following.

Theorem 7.1. Let κ be an infinite cardinal.

(i) If G has a normal tree of height ⩽ κ, then G has a linked normal tree of height ⩽ κ.

(ii) If G has a normal tree of height < κ, then G has a linked normal tree of height < κ.

(Compare with Theorem 9.1 below.)

Proof. Let T be any normal tree for G. We first consider the case of κ = ω for the second assertion, and assume that ht(T) = n < ω. As is easily shown by induction on n, any path in a graph with a normal tree of height ⩽ n has length at most f(n), where f(n) depends on n but not on the graph. Now use Jung’s theorem to obtain a linked normal tree T̃ for G of height ⩽ ω. Since G has no path of length > f(n), T̃ has finite height, as required.

We now turn to the general case. We shall prove assertions (i) and (ii) simultaneously, showing that G has a linked normal tree T̃ such that

ht T̃(v) < ht_{T} (v) + ω

for every vertex v ^{∈} G. Let us start by well-ordering the vertices of G, proceeding level by level up the tree T. More precisely, let us fix any well-ordering on V (G) in which x comes before y whenever ht_{T} (x) < ht_{T} (y).

Call a tree T′ defined on a subset of V (G) promising if T′ is normal for the subgraph G [ T′] it induces in G, if it has properties (L1) and (L3) with respect to G [ T′], and if, for every component C of G − T′, the vertices of T′ with a neighbour in C form a chain. (We do not, however, require property (L2) for the time being.) We shall construct our tree T̃ inductively, as the nested union of promising trees T̃_{α}, where α runs over some initial segment of the ordinals.

Let T̃_{0} = { x_{0} }, where x_{0} is the root of T. Now assume that, for some ordinal α and all β < α, we have constructed promising trees T̃_{β} so that T̃_{γ} is a down-closed subtree of T̃_{β} whenever γ < β < α. Then

T̃′_{α} := ⋃_{β<α} T̃_{β}

is again a promising tree.

If T̃′_{α} contains all the vertices of G, we terminate the construction and set T̃ := T̃′_{α}. Otherwise let x_{α} be the least vertex in the well-ordering of V (G) that is not in T̃′_{α}, let C_{α} be the component of G − T̃′_{α} containing x_{α}, and let N_{α} be the set of vertices in T̃′_{α} with a neighbour in C_{α}. Since T̃′_{α} is promising, N_{α} is a chain in T̃′_{α}; let S_{α} be a minimal length cofinal subset of N_{α}.

Let v_{α} be a neighbour of S_{α} in C_{α} at minimal distance from x_{α}. (In particular, set v_{α} := x_{α} if x_{α} is adjacent to a vertex in S_{α}.) Let T̃_{α} be obtained from T̃′_{α} by placing v_{α} directly above N_{α}. (Thus, v_{α} is above every point in the down-closure of N_{α}, and incomparable with any other point of T̃′_{α}.) It is easily checked that T̃_{α} is again a promising tree. (For property (L3), notice that if v_{α} is the successor of some vertex x in T̃_{α}, then x = max S_{α} and hence S_{α} = { x }, so v_{α} is adjacent to x.)

The tree T̃ thus constructed is itself promising, i.e. it is normal for G and has properties (L1) and (L3). In order to show that T̃ is linked, it remains to verify property (L2). Let x ^{∈} T̃ be given, and let α be such that x = v_{α}. We prove that ⌊x⌋T̃ = V (C_{α}).

To show that V (C_{α}) ⊆ ⌊x⌋T̃, let y ^{∈} V (C_{α}). Then y is not below x in T̃, because ⌈x̊⌉T̃ ⊆ T̃′_{α}. Moreover, y is connected to x by a path in C_{α}. By (2.1) and the normality of T̃, this means that y is not incomparable with x either (in T̃), so y ^{∈} ⌊x⌋T̃ as claimed.

For the reverse inclusion, suppose that ⌊x⌋T̃ contains a vertex y that is not in C_{α}; let y be chosen minimal in ⌊x⌋T̃ with this property. Clearly, y ≠ x. Moreover, y is not adjacent to x: since x ^{∈} V (C_{α}), any vertices of T̃\V (C_{α}) adjacent to x must be in N_{α}, i.e. below x. Since T̃ satisfies (L3), we deduce that y is not a successor of x in T̃.

Now let β > α be such that y = v_{β}. Let s be a vertex of S_{β} above x; such a vertex exists, because S_{β} is cofinal in ⌈ẙ⌉T̃ but ⌈x⌉T̃ is not. Since s has a neighbour in C_{β} and V (C_{β}) ∩ T̃′_{α} = ∅, there exists an s–y path in G that avoids T̃′_{α}. But s ^{∈} V (C_{α}) by the minimality of y, so this means that also y ^{∈} V (C_{α}), as claimed.

It remains to show that ht T̃(v) < ht_{T} (v) + ω for every vertex v ^{∈} G. For each v, find α such that v = v_{α}, and set x(v) := x_{α}. (Thus, x(v) was the ‘target vertex’ when v was added to T̃.) By the choice of the vertices v_{α} in the construction of T̃, each vertex x of the form x_{α} is such that the vertices v with x(v) = x form a finite interval in T̃, with x itself at the top. By (L3), this means that these vertices induce a path P (x) in G.

Now consider a fixed vertex v ^{∈} G. Let again α be such that v = v_{α}, and put x := x_{α} = x(v). As neither v nor x is in T̃′_{α}, the definition of x_{α} implies that x precedes v in the well-ordering of V (G) on which the construction of T̃ was based. Hence, either x ⩽_{T} v or the two vertices are incomparable in T. In the latter case, however, the path P (x) contains a vertex w <_{T} x (2.1), giving x = x(w) >_{T} w with a contradiction. Therefore x ⩽_{T} v.

We have now shown that

v ⩽T̃ x(v)  and  x(v) ⩽_{T} v

for every v ^{∈} V (G). In order to show that ht T̃(v) < ht_{T} (v) + ω for every v, it therefore suffices to show this for vertices of the form x_{α}: then

ht T̃(v) ⩽ ht T̃(x(v)) < ht_{T} (x(v)) + ω ⩽ ht_{T} (v) + ω

for every vertex v of G, as desired.

We apply induction along our well-ordering of V (G). Let x ^{∈} V (G) of the form x_{α} be given, and choose α minimal such that x = x_{α} for this x. If α = 0, then x is the root of both T and T̃, so its height is 0 in both trees. Let us therefore assume that α > 0.

Since ht T̃(x) is, roughly, the supremum of the T̃-heights of the vertices in S_{α}, let us try to estimate these. Since x(v) ⩽_{T} v for every v <_{T} x, our well-ordering of V (G) implies that ⌈x̊⌉_{T} ⊆ T̃′_{α}. Therefore every vertex of C_{α} is connected to x by a path that avoids ⌈x̊⌉_{T} (namely, a path in C_{α}). By (2.1) for T, this means that V (C_{α}) ⊆ ⌊x⌋_{T}.

Since every vertex in S_{α} is adjacent to a vertex in C_{α}, the above inclusion means that S_{α} ⊆ ⌊x⌋_{T} ∪ ⌈x⌉_{T}. As the set ⌊x⌋_{T} ∪ ⌈x⌉_{T} is down-closed in T and x(s) ⩽_{T} s for every s, we deduce that

x(s) ^{∈} ⌊x⌋_{T} ∪ ⌈x⌉_{T}

for every s ^{∈} S_{α}. Moreover, the vertex x(s) precedes x in the well-ordering of V (G) (because s ^{∈} T̃′_{α}, and α is minimal with x = x_{α}), so it cannot be in ⌊x⌋_{T}. Thus, x(s) ^{∈} ⌈x⌉_{T}, i.e.

x(s) <_{T} x  for all s ^{∈} S_{α}.

We may therefore apply the induction hypothesis to these vertices x(s), and choose a number ϵ_{s} < ω for each s such that

ht T̃(x(s)) < ht_{T} (x(s)) + ϵ_{s}.

Let ℓ_{x} be the length of the path P (x). The height of x in T̃ can then be bounded as follows:

ht T̃(x) = sup { ht T̃(s) + 1 | s ^{∈} S_{α} } + ℓ_{x}
⩽ sup { ht T̃(x(s)) + 1 | s ^{∈} S_{α} } + ℓ_{x}
⩽ sup { ht_{T} (x(s)) + ϵ_{s} | s ^{∈} S_{α} } + ℓ_{x}
< ht_{T} (x) + ω.

(The last inequality again uses the fact that x(s) <_{T} x for all s ^{∈} S_{α}.) □

As a first immediate consequence of Theorem 7.1, let us note the following analogue to Corollary 1.5:

Corollary 7.2. G has a linked normal tree of ordinal height ⩽ |G|.

Proof. Pick a well-ordering of V (G) of order type |G|. This is a normal tree of height ⩽ |G|; apply Theorem 7.1. □

As subgraphs of a graph with a normal tree of height κ again have normal trees of at most this height, Theorem 7.1 allows us to say the same about linked normal trees (which, once more, does not seem obvious from first principles):

Corollary 7.3. Let κ be an infinite cardinal. If G has a linked normal tree of height ⩽ κ, then so does every connected subgraph of G. □

We have now seen that if G has a normal tree of height ⩽ κ, then this tree may be assumed to be either linked (Theorem 7.1) or a normal expansion tree (Corollary 6.4). Unfortunately, we cannot have both strengthenings at once; indeed, G need not have a linked normal expansion tree of any height. Our graph K from Proposition 3.1, a TK_{ℵ_{1}} in which every edge has been subdivided once, is a counterexample:

Proposition 7.4. K does not have a normal expansion tree satisfying (L3).

Proof. As before, let X ⊆ V (K) denote the set of vertices of infinite degree, and S the set of vertices of degree 2. Suppose T is a normal expansion tree for K satisfying (L3). By Proposition 5.2, T^{<ω_{1}} is a narrow ℵ_{1}-tree; let B denote its central branch. For each t ^{∈} B, let t^{+} denote the successor of t on B. Note that, by (L3), t and t^{+} are adjacent. By (5.1), K [ B] is ℵ_{1}-cohesive. We shall derive a contradiction by finding a vertex z ^{∈} B that separates K [ B] into uncountably many components.

Let z be any vertex of uncountable degree in K [ B]; we may assume that such a vertex exists, since otherwise K [ B] would have uncountably many (countable) components, completing the proof. Then z is in X, and the set S′ of its upper neighbours on B is contained in S. We show that z separates the vertices of S′ pairwise in K [ B]; since S′ is uncountable—as z has countable height, it has only countably many neighbours below—this will complete the proof.

Let s, s′ ^{∈} S′, and suppose K [ B] contains an s–s′ path
sx_{1}s_{1}x_{2} … x_{n−1}s_{n−1}x_{n}s′

avoiding z. Since s is adjacent to s^{+} and its only neighbours are z and x_{1}, we see that s^{+} = x_{1} (as z < s). Similarly, s_{1}^{+} = x_{2} (it cannot be x_{1}, since x_{1} = s^{+} and s ≠ s_{1}), and by induction s_{i}^{+} = x_{i+1} for all i. Repeating the argument for s′, we find that its successor on B cannot be x_{n} (since s_{n−1}^{+} = x_{n}), and hence must be its only other neighbour, z. But this contradicts the fact that z < s′ by definition of S′. □

8. The structure of cohesive graphs

The concept of cohesion, although we introduced it with normal trees in mind, appears to be of interest quite independently: as a notion of connectedness tailored specifically to infinite graphs. In this section, we shall try to see what cohesive graphs look like.

Recall that every ℵ_{0}-cohesive graph contains a particular type of ℵ_{0}- cohesive graph, namely, a ray. In this sense, rays are the ‘canonical’ ℵ_{0}-cohesive subgraphs. For uncountable κ, there is a similar result: we shall see that every κ-cohesive graph has a K_{κ}-minor—it has a subgraph HK_{κ} from which a K_{κ} can be obtained by contracting connected sets of vertices. Conversely, such graphs HK_{κ} are essentially κ-cohesive, so these are the canonical κ-cohesive subgraphs for κ > ℵ_{0}.

Our second result in this section characterizes the cohesive graphs of regular size κ by their tree structure: their shape is that of a narrow κ-tree, with good linking properties along its branches.

Let X be a graph. A graph will be called a TX (where ‘T’ stands for ‘topological’) if it is isomorphic to a subdivision of X. Similarly, a graph H will be called an HX (here, ‘H’ comes from ‘homomorphism’) if its vertex set admits a partition

V (H) = ⋃ { V_{x} | x ^{∈} V (X) }

into connected sets of vertices such that, for all x, y ^{∈} V (X), H contains a V_{x}–V_{y} edge if and only if xy is an edge of X. The sets V_{x} are called the branch sets of this HX, and the edges of H between different branch sets are its main edges. The HX is called lean if

(i) for any adjacent x, y ^{∈} V (X) there is only one V_{x}–V_{y} edge in H; and (ii) each branch set spans a tree in H such that every leaf and every ray in

this tree are incident with a main edge. In a lean HX, the cardinality of a branch set V_{x} is either finite or equal to the degree of x in X. Thus if X is infinite and H is a lean HX, then |H| = |X|. It is easy to see that every HX contains a lean HX as a subgraph.

Note that every TK_{κ} is also a lean HK_{κ}. Conversely, it was shown by Jung [ 12 ] that, for regular κ > ℵ_{0}, every HK_{κ} contains a TK_{κ}. (This need not be so for singular κ or κ = ℵ_{0}.) Thus, for κ > ℵ_{0} regular, TK_{κ} and HK_{κ} containment are equivalent:

(8.1) For κ > ℵ_{0} regular, G contains an HK_{κ} if and only if it contains a TK_{κ}.

As we observed earlier, any TK_{κ} has cohesion κ. This is in fact true for every HK_{κ}:

(8.2) For every infinite cardinal κ, every lean HK_{κ} has cohesion κ.

Indeed, let H be a lean HK_{κ}. Since |H| = |K_{κ}| = κ, the cohesion of H cannot be greater than κ. We thus have to show that H is κ′-cohesive for every infinite cardinal κ′ ⩽ κ. Let S ⊆ V (H) have size λ < κ′. Then H has a branch set U that avoids S; let C be the component of G − S containing this branch set. We show that C contains all but λ of the vertices of H. (Here as below, if κ′ = ℵ_{0} then any occurrence of ‘λ’ is to be read as ‘finite’ or ‘finitely many’.)

Since every branch set of H contains a vertex adjacent to a vertex in U, any branch set not contained in C meets S. Hence, there are at most λ such branch sets, and at most λ^{2} = λ main edges between them (because H is lean). Let V be a branch set not contained in C, and let F be the subgraph of H induced by V \V (C). Then F is a forest in which at most λ vertices are incident with a main edge (again because H is lean), so |F | ⩽ λ. The union of all these forests, which contains precisely the vertices of H\C, thus has at most (in fact, exactly) λ vertices. This completes the proof of (8.2).

Robertson, Seymour and Thomas—see (2.3) in [ 14 ]—have shown the following.*

Theorem 8.3. If G is κ-cohesive with κ > ℵ_{0}, then G contains an HK_{κ}.

By (8.2) and Theorem 8.3, a graph has a κ-cohesive subgraph if and only if it contains a (lean) HK_{κ}. Lean HK_{κ}s (or TK_{κ}s, when κ is regular) are thus the ‘canonical’ examples of κ-cohesive subgraphs.

* In their own terminology, Robertson, Seymour and Thomas show that any graph with a ‘κ-haven’ (κ > ℵ_{0}) has a K_{κ}-minor, i.e. contains an HK_{κ}. It is clear that every κ-cohesive graph has such a ‘κ-haven’.

Note that (8.2) and Theorem 8.3 together extend Corollary 5.10 to arbitrary infinite κ (regular or singular): if G is λ-cohesive and κ < λ, then G has a κ-cohesive subgraph.

We remark that for singular κ, the strengthening of Theorem 8.3 to TK_{κ} (rather than HK_{κ}) is false. For example, consider the graph obtained from the disjoint union of ω complete graphs G_{n} of size ℵ_{n} by joining all the vertices of G_{n} to all the vertices of G_{n+1} (for every n < ω). This graph is ℵ_{ω}-cohesive but has no vertex of degree ℵ_{ω}, and hence contains no TK_{ℵ_{ω}}.

As a consequence of (8.2) and Theorem 8.3, we can now rephrase dispersion in terms of separation from a well-specified type of subgraph, just as in the classical countable case:

Corollary 8.4. For every κ > ℵ_{0} and U ⊆ V (G), the following assertions are equivalent.

(i) U is κ-dispersed in G; (ii) any lean HK ⊆ G, where K is any complete graph, can be separated

from U in G by < κ vertices; (iii) any lean HK_{κ} ⊆ G can be separated from U in G by < κ vertices. When κ is regular, ‘lean HK_{κ}’ in (ii) and (iii) may be replaced with ‘TK_{κ}’.

Proof. (i)→(ii) follows from (5.5) and (8.2). (ii)→(iii) is trivial. In order to prove (i) from (iii), let H ⊆ G be κ-cohesive, find an HK_{κ} in H (by Theorem 8.3), and inside it a lean HK_{κ}. Using (iii), let S ⊆ V (G) be a set of size < κ that separates this HK_{κ} from U. Since H is κ-cohesive, H − S has one component that contains all but < κ of the vertices of H. Hence, our HK_{κ} meets this component, and so U does not. Therefore |U ∩ V (H)| < κ, and U is κ-dispersed as claimed.

The proof of the TK_{κ} version for κ regular is the same as above, with an additional application of (8.1) in the proof of (iii)→(i). □

Corollary 8.4 allows us to generalize Corollary 5.9 to arbitrary κ:

Corollary 8.5. For every infinite cardinal κ, any κ-dispersed set U ⊆ V (G) is also λ-dispersed for all λ > κ. □

Using Corollary 8.4, we may reformulate the uncountable case of Theorem 6.1 as follows: for regular κ > ℵ_{0}, G has a normal tree of height ⩽ κ if and only if V (G) is the union of ⩽ κ sets each of which can be separated from any lean HK_{κ} ⊆ G (equivalently, from any TK_{κ}) by < κ vertices. Is the same true for κ = ℵ_{0}? (Note that ‘only if’ follows from Proposition 5.2, applied to the HK_{ℵ_{0}}, and (2.1), applied to the levels of T.) The ‘stronger’ version of this, with TK_{ℵ_{0}} rather than HK_{ℵ_{0}}, would be particularly interesting: it would strengthen and unify Jung’s theorem with Halin’s [ 11 ] result that every connected graph not containing any TK_{ℵ_{0}} has a normal spanning tree.

Our second theorem in this section describes the outward structure of the cohesive graphs of size κ when κ is regular: their shape is ‘tall and narrow’, given by a narrow κ-tree. In a sense, this result is dual to Proposition 5.7: there, the dual notion of a κ-dispersed set is characterized as being ‘short and (possibly) wide’ in a suitable normal tree.

Theorem 8.6. Assume that G has regular size κ. The following statements are equivalent:

(i) G is cohesive; (ii) G has a linked normal tree which is a narrow κ-tree; (iii) G has a normal expansion tree which is a narrow κ-tree.

Proof. (i)→(ii) By Corollary 7.2, G has a linked normal tree T of height ⩽ κ. Thus T = T^{<κ}, which is a narrow κ-tree by Proposition 5.2.

(ii)→(i) Let T be a linked normal narrow κ-tree for G. To show that G is κ-cohesive, let X ⊆ V (G) with |X| < κ. As κ is regular, there is an α < κ such that X ⊆ T^{<α}. Let t be the point on the central branch of T at level α. Since T is linked, ⌊t⌋ spans a connected subgraph of G − X. Since T is narrow, this subgraph contains all but < κ of the vertices of G.

(i)→(iii) By Corollary 6.5, G has a normal expansion tree T of height ⩽ κ. Thus T = T^{<κ}, which is a narrow κ-tree by Proposition 5.2.

(iii)→(i) Let Ṫ be a normal partition tree for G with an expansion T as in (iii). By (4.1), Ṫ is a narrow κ-tree, its central branch expanding to that of T. To show that G is κ-cohesive, we proceed as in the proof of (ii)→(i). Let X ⊆ V (G) with |X| < κ. As κ is regular, there is an α < κ such that t(x) ^{∈} Ṫ^{<α} for every x ^{∈} X. Let t be the point on the central branch of Ṫ at level α. Since Ṫ is well linked and the partition sets V_{t} are connected in G, the expansion of ⌊t⌋ induces a connected subgraph H of G − X. The minimal vertex v of H satisfies t(v) = t, so v lies on the central branch of T. Since T is narrow, H contains all but < κ of the vertices of G. □

By the same proof as above, the implications (i)→(ii) and (i)→(iii) in Theorem 8.6 are valid for singular κ. Their converses, however, are easily seen to be false.

As we saw earlier, every κ-cohesive graph contains a κ-cohesive graph of size κ, namely, a lean HK_{κ} or a ray. Thus, the κ-cohesive graphs of size κ are the ‘essential’ ones, and it is the shape of these graphs that is decribed in Theorem 8.6. This makes it desirable, however, to determine conditions under which a subgraph H ⊆ G of size κ can be extended to a κ-cohesive subgraph of G, still of size κ: the shape of this extension, and hence that of H, will then be as in Theorem 8.6.

Let us call a set U ⊆ V (G) κ-cohesive in G if |U| ⩾ κ and, for every X ⊆ V (G) with |X| < κ, the graph G − X has a component containing all but < κ of the vertices in U. This is a weakening of the statement that U induces a κ-cohesive subgraph, in which case U is clearly κ-cohesive in G. Note that with U all its subsets of size ⩾ κ are κ-cohesive in G, and U is κ-cohesive in G as soon as all its subsets of size κ are.

A typical example of a κ-cohesive set is the set of ‘main’ vertices in a TK_{κ}, which is itself totally disconnected, but no small set can separate it in G into two or more large subsets. More generally, it is clear (and will be used below) that every set of ⩾ κ vertices in a κ-cohesive graph is κ-cohesive in that graph. In fact, these are the canonical examples of ‘small’ κ-cohesive sets: as the following proposition shows, every κ-cohesive set of size κ in G is contained in some κ-cohesive subgraph (of the same size), even when G itself is not κcohesive.

Proposition 8.7. Let κ be a regular cardinal, and suppose that U ⊆ V (G) is a κ-cohesive set of size κ in G. Then U is contained in some cohesive subgraph H ⊆ G of size κ.

Proof. As |U| = κ, U is trivially the union of at most κ κ-dispersed sets. By (6.2), G has a normal expansion tree T such that U ⊆ T^{<κ}. Exactly as in the proof of Proposition 5.2, our assumption that U is κ-cohesive in G and the fact that U ⊆ T^{<κ} imply that ⌈U⌉ is a narrow κ-tree. Set W := { V_{t(v)} | v ^{∈} ⌈U⌉ } (keeping the notation of Section 4); W is still a narrow κ-tree (in particular, |W | = κ), and it contains U. Moreover, W is a normal expansion tree. Thus, by Theorem 8.6 (iii)→(i), the subgraph H ⊆ G induced by W is cohesive and has size κ. □

Corollary 8.8. Let κ be a regular cardinal. If G is κ-cohesive, then every subgraph of size κ can be extended to a cohesive subgraph of the same size.

9. Bounding branch length: the tree structure of TK_{κ}-free graphs

In this short section we shall kill two birds with one stone. Unlike in the last section, where we looked at the tree structure of cohesive graphs, we shall now determine the structure of the graphs not containing any κ-cohesive graph, for regular κ > ℵ_{0}. By (8.1) and Theorem 8.3, these are precisely the TK_{κ}-free graphs (those without a TK_{κ} subgraph), so we will get a structure theorem for those graphs for free.

On the other hand, our characterization of those graphs involves various equivalent conditions, each asserting the existence of certain normal trees with bounded branch lengths. The equivalence of these conditions, which involve our various notions of linkedness, complements our results from Sections 6 and 7 (where the bound was on the overall tree height), and thus completes our list of existence theorems for normal trees.

Theorem 9.1. For every regular uncountable cardinal κ, the following assertions are equivalent:

(i) G is TK_{κ}-free; (ii) G has no κ-cohesive subgraph; (iii) every normal expansion tree for G has branch lengths < κ; (iv) G has a normal expansion tree with branch lengths < κ;

(v) G has a linked normal tree with branch lengths < κ; (vi) G has a normal tree with branch lengths < κ.

Proof. Assertions (i) and (ii) are equivalent by (8.1) and Theorem 8.3. We show (ii)→(iii)→(iv)→(vi)→(ii) and (ii)→(v)→(vi).

(ii)→(iii) follows from (5.1). (iii)→(iv) follows from Theorem 4.2. (iv)→(vi) and (v)→(vi) are trivial. (vi)→(ii) follows from (5.4).

It remains to prove (ii)→(v), so assume that (ii) holds. Then (vi) holds as well (by the above), so by Theorem 7.1 G has a linked normal tree T of height ⩽ κ. We claim that every branch of T has length < κ. So let B ⊆ T be a branch. Then B is κ-cohesive in G. Indeed, if X ⊆ V (G) has size < κ, there exists an α < κ with X ⊆ T^{<α} (since κ is regular). Thus if t is the point on B at level α, then X ∩ ⌊t⌋ = ∅. But ⌊t⌋ induces a connected subgraph in G by (L2), completing the proof that B is κ-cohesive in G. By Proposition 8.7, then, G has a κ-cohesive subgraph, which contradicts (ii). □

We remark that the equivalence of (i) and (vi) in Theorem 9.1, so easily obtained here, is tantamount to the main result of [ 6 ]. Note also that the theorem generalizes Halin’s [ 11 ] result that every connected TK_{ℵ_{0}}-free graph has a normal spanning tree.

The implications (i)→(iii) and (ii)→(iii) in Theorem 9.1 do not extend to singular κ. For example, it is easy to furnish a vertex sequence of singular length κ with edges in such a way that it becomes a long ray in the arising graph but this has no κ-cohesive subgraph. Moreover, we have seen that (i)→(ii) fails for some singular cardinals κ, so (i)→(iv) and (i)→(vi) fail for these κ, too (by (5.4)). We do not know, however, whether some or all of (ii), (iv), (v) and (vi) are still equivalent for singular κ.

Note that, by our proof of (ii)→(v), the conditions in the theorem actually imply that every linked normal tree for G of height ⩽ κ has branches all shorter than κ. However, G may have linked normal trees of larger height, which then have longer branches: for example, if G is obtained from κ disjoint rays by adding two new vertices adjacent to every other vertex, then G is TK_{κ}-free but has a linked normal tree of height κ + 1 consisting of a single branch.

Finally, there is a similar characterization to Theorem 9.1 of the TK_{ℵ_{0}}-free graphs, to be found in [ 10 ]. On the other hand, we may obtain a structure theorem for the rayless graphs from Theorem 9.1 if we replace κ with ω and condition (i) with the condition that G is rayless (i.e. contains no infinite path); the proof remains the same as above.

Of course, the description in Theorem 9.1 of the TK_{κ}-free graphs is but one of its several facets. Another is the equivalence between its assertions (iv),

(v) and (vi), extending Corollary 6.4 and Theorem 7.1. Furthermore, we have the following analogue to Corollaries 6.6 and 7.3:

Corollary 9.2. Let κ be a regular uncountable cardinal.

(i) If G has a normal expansion tree with branch lengths < κ, then so does every connected subgraph of G.

(ii) If G has a linked normal tree with branch lengths < κ, then so does every connected subgraph of G. □

Clearly, Corollary 9.2 remains true if we replace the words ‘subgraph’ with ‘topological minor’. (H is a topological minor of G if G contains a subdivision of H.) In fact, Theorem 9.1 may be viewed as a Kuratowski-type characterization of those connected graphs that admit a normal tree with all branches < κ long: G has such a tree if and only if it does not contain a TK_{κ}. Is there a similar characterization when we replace the strict inequality “< κ” with “⩽ κ”? In other words, is there a ‘forbidden topological minor’ characterization of the graphs admitting a normal tree of height ⩽ κ?

Formally, the property of admitting a normal tree of height ⩽ κ (for any infinite cardinal κ) lends itself to such a characterization: as an easy application of Theorem 6.3, one can show that the property of admitting such normal trees is closed under taking topological minors. In practice, however, it is not clear whether there is a small set of forbidden topological minors characterizing this property:

Problem. For κ an infinite cardinal, is there a small set of graphs such that G admits a normal tree* of height ⩽ κ if and only if G has no subgraph isomorphic to a subdivision of a graph in this set? In particular, is there a simple such characterization of the connected graphs admitting a normal spanning tree in Jung’s sense?

A possible candidate for such a set of forbidden topological minors might be the graph indicated towards the end of Section 6 (generalized to arbitrary κ).

* equivalently, a normal expansion tree, or a linked normal tree; cf. Cor. 6.4 and Thm. 7.1

10. Further remarks and open problems

We saw early in the paper that well linked normal trees, however desirable they may be, do not generally exist for arbitrary connected graphs. We then went on to consider various weakenings of well-linkedness, trying to secure general existence while preserving as much of the strength of the original concept as possible.

One weakening we did not consider is to allow our trees not to be wellfounded. In principle, this would make sense: normality can be defined as usual, and (2.1) carries over. However, as the proof of Proposition 3.1 shows, such a weakening will not result in a notion of a tree that exists for every connected graph.

Still, what would be a reasonable definition of a not necessarily wellfounded well linked normal tree (nonewelflinot, for short)? One property of ordinary well linked normal trees that might serve as the definition for a nonewelflinot is that all intervals in the tree order induce connected subgraphs. A slightly stronger requirement (equivalent in the well-founded case) is that for any two points t < t′ in the tree there is an ascending t–t′ path in the graph, i.e. a path t = x_{1} … x_{n} = t′ such that x_{i} < x_{i+1} for all i = 1, …, n − 1. Thus, the tree order is precisely the transitive closure of the ‘directed’ adjacency relation on the vertex set, each edge being directed upwards (say).

Such trees have been studied by the first author [ 1 ]. In [ 4 ], it was shown that if G is |G|-connected, it contains a nonewelflinôt consisting of a single branch. (There need not be a long ray on V (G) as defined in Section 2.) Another result, from [ 1 ], may be worth quoting here—particularly as Proposition 3.1 shows that not every graph has a nonewelflinot:

Theorem 10.1. [ 1 ] Let κ be an infinite cardinal.

(i) Every κ-connected graph with no independent vertex (sub)set of size κ has a nonewelflinot.

(ii) It is consistent that every graph with no uncountable independent set of vertices has a nonewelflinot.

Forbidding large independent sets can also help to secure the existence of an ordinary (i.e. well-founded) well linked normal tree. It was shown in [ 2 ] that any connected graph with no infinite independent set of vertices has a well linked normal tree. The proof, moreover, implies the following bound on the tree’s height:

Theorem 10.2. [ 2 ] If G has no infinite independent set and admits a normal tree of height α, then G has a well linked normal tree of height at most |α|.

We conclude with a list of our main open problems. Let κ be an infinite cardinal.

Problems. 1. Which graphs admit a well linked normal tree?

2. Does every connected graph admit a normal tree whose branch tails all induce connected subgraphs?

3. Is there a small set of graphs such that G admits a normal tree of height ⩽ κ if and only if it has no subgraph isomorphic to a subdivision of a graph in this set? In particular, is there a simple such characterization of the connected graphs admitting a normal spanning tree in Jung’s sense?

4. Does G have a normal spanning tree if its vertex set is the union of countably many sets each separated from any TK_{ℵ_{0}} ⊆ G by a finite set (depending on the choice of the TK_{ℵ_{0}})?

5. Characterize the graphs admitting a normal tree of height < κ.

6. Does every graph as in (5.) have a normal expansion tree of height < κ?

7. What do the graphs of cohesion κ look like?

8. Can normal trees be used to characterize the graphs without a K_{κ} minor? (See [ 14 ] for characterizations of these graphs in terms of tree-decom-positions.)

References

[ [ 1 ]] J. M. Brochet, Covers of graphs by infinite generalized paths, submitted. [ [ 2 ]] J. M. Brochet, Paths and trees in graphs with no infinite independent set, submitted. [ [ 3 ]] J. M. Brochet, Tree partitions of infinite graphs into fully connected subgraphs, submit-

ted. [ [ 4 ]] J. M. Brochet and M. Pouzet, Gallai-Milgram properties for infinite graphs, Discrete

Math. 95 (1991), 23–47. [ [ 5 ]] J. M. Brochet and R. Diestel, Normal tree orders in infinite graphs II, in preparation. [ [ 6 ]] R. Diestel, The structure of TK_{a}-free graphs, J. Combin. Theory B 54 (1992), 222–238. [ [ 7 ]] R. Diestel, The end structure of a graph, Discrete Math. 95 (1991), 69–89. [ [ 8 ]] R. Diestel and I. Leader, A proof of the bounded graph conjecture, Invent. math. 108

(1992), 131–162. [ [ 9 ]] R. Diestel, The classification of finitely spreading graphs, submitted. [ [ 10 ]] R. Diestel, The depth-first search tree structure of TK_{ℵ_{0}}-free graphs, J. Combin. Theo-

ry B (to appear). [ [ 11 ]] 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.

[ [ 12 ]] H. A. Jung, Zusammenzüge und Unterteilungen von Graphen, Math. Nachr. 35 (1967),

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

1–22.

[ [ 14 ]] N. Robertson, P.D. Seymour and R. Thomas, Excluding infinite minors, in: R. Diestel (Ed.), Directions in Infinite Graph Theory and Combinatorics, (Topics in Discrete Mathematics 3), North-Holland Publ. Co., Amsterdam 1992.

Jean-Michel Brochet Groupe LMDI Université Claude Bernard (Lyon 1) F-69622 Villeurbanne Cedex France Reinhard Diestel Faculty of Mathematics (SFB 343) Bielefeld University D-4800 Bielefeld 1, P.O. Box 100131 Germany