An Accessibility Theorem for Infinite Graph Minors

Reinhard Diestel

We prove the following recent conjecture of Halin. Let Γ_{0} be the class of all graphs, and for every ordinal μ > 0 let Γ_{μ} be the class of all graphs containing infinitely many disjoint connected graphs from Γ_{λ}, for every λ < μ. Then a graph lies in all these classes Γ_{μ} if and only if it contains a subdivision of the infinite binary tree.

1. Halin’s conjecture

In his recent collection [ 2 ] of open problems about infinite graphs, Halin defines the following hierarchy of graphs. He defines Γ_{0} to be the class of all graphs (finite or infinite), and for each ordinal μ > 0 he defines Γ_{μ} as the class of all graphs containing, for each λ < μ, infinitely many disjoint connected^{1} graphs from Γ_{λ}. Thus, Γ_{1} is the class of infinite graphs, Γ_{2} is the class of all graphs containing infinitely many disjoint connected infinite graphs (or equivalently, either infinitely many disjoint rays or infinitely many disjoint infinite stars), and so on.

Halin then asks which graphs, if any, lie in every Γ_{μ}. He notes that Γ_{λ} ⊇ Γ_{μ} whenever λ < μ, and that any graph with a minor in Γ_{μ} is itself in Γ_{μ} (induction on μ). We might add the observation that the sequence of Γ_{μ}s does not become stationary, i.e. that for every ordinal μ there is a (connected) graph in Γ_{μ} ∖ Γ_{μ+1}; this, too, follows easily by induction on μ.

Intuitively, it may be natural to consider not the graph properties Γ_{μ} themselves but their complements \overline{Γ}_{μ}. As observed above, these classes are closed under taking minors, and they form an increasing sequence \overline{Γ}_{0} ⊆ \overline{Γ}_{1} ⊆ …. The question then arises whether every graph is captured by this sequence, and if not then which graphs are.

Following Halin, let us define as the order o(G) of a graph G the least ordinal μ (if one exists) such that G /^{∈} Γ_{μ}. Note that if G has an order and H is a minor of G, then H too has an order and o(H) ⩽ o(G).

Which graphs, then, have an order? At first glance, this may look like a difficult question. Indeed, it even seems unclear whether or not every graph has an order. As Halin observes, however, there is a simple sufficent condition for not having an order: if a connected graph G contains infinitely many disjoint copies of itself, then induction on μ shows at once that G^{∈} Γ_{μ} for all ordinals μ.

1 The connectedness requirement is essential: without it, every Γ_{μ} with μ > 0 would just be the class of infinite graphs.

A simple example of such a graph is the infinite binary tree T_{2}. Halin conjectured that, up to taking minors (even topological minors), it is the unique canonical example:

Conjecture. (Halin [ 2 ]) A graph has an order if and only if it does not contain a subdivision of the infinite binary tree T_{2}.

The conjecture implies in particular that our simple sufficient condition for not having an order is also necessary (after closuring it ‘upwards’ under minors):

Corollary. A graph has no order if and only if it has a connected minor that contains infinitely many disjoint copies of itself.

The purpose of this note is to prove Halin’s conjecture.

2. Terminology and prerequisites

Any notation not explained below is taken from [ 1 ]. Minors of infinite graphs are defined just as for finite graphs; note that the branch sets (the connected sets of vertices to be contracted) may now be infinite.

All trees we consider are rooted trees. If T is a tree with root r, we write x ⩽_{T} y for vertices x, y ^{∈} T if x ^{∈} rT y, i.e. if x lies on the path in T from r to y. This is a partial ordering on V (T) with r as its least element, in which every element other than r has a unique lower (= lesser) neighbour. The maximal elements in this partial order will be called the leaves of T. (Thus, r is a leaf if and only if T = { r }; any other vertex of T is a leaf if and only if its degree is 1.) When κ is a cardinal, we denote by T_{κ} the tree in which every vertex has exactly κ upper (= greater) neighbours; the binary tree, for example, is denoted by T_{2}.

Note that if T′ is a subtree of T then T′ has a unique minimal vertex r′, because incomparable (minimal) vertices are separated by their infimum. Unless otherwise stated, we take r′ to be the root of T′; then its tree order ⩽_{T′} coincides with the order induced on T′ by ⩽_{T}. Given a vertex t ^{∈} T, we denote by T^{t} the subtree of T with vertex set { t′ | t ⩽_{T} t′ } (and root t).

A ray is a one-way infinite path. A ray t_{0}t_{1} … in a tree T is free in T if t_{i+1} is the unique upper neighbour of t_{i} in T, for all i = 0, 1, ….

We assume that the reader is familiar with the basic facts about treedecompositions, e.g. as explained in [ 1, Ch. 12 ]. In particular, we shall use freely the basic separation lemma for tree-decompositions, [ 1, Lemma 12.3.1 ].

3. Proof of Halin’s conjecture

In this section we prove that every graph not containing a subdivision of T_{2} has an order. Clearly, a graph G contains a subdivision of T_{2} if and only if it has a T_{2} minor (which we write as T_{2} ≼ G). The graphs without a T_{2} minor have been characterized by Seymour and Thomas, as follows:

Theorem 1. (Seymour & Thomas [ 3 ]) A graph has no T_{2} minor if and only if it has a tree-decomposition (T, (V_{t})_{t^{∈}T}) into finite parts such that T_{2} ⋠ T and for every ray t_{0}t_{1} … ⊆ T there is an integer k such that |V_{i} ∩ V_{i+1}| < k for infinitely many i.

(In [ 3 ], this result is stated for T_{ℵ_{0}} rather than for T_{2}. However, since T_{2} ≼ T_{ℵ_{0}} ≼ T_{2}, the two versions are equivalent.)

Theorem 1 explains the structure of the graphs G ⋡ T_{2} in terms of the structure of the trees T ⋡ T_{2}. This is a non-trivial step, for the trees without a T_{2} minor are indeed easier to handle. For example, it is well known and easy to prove that a tree has no T_{2} minor if and only if it can be pruned down to the empty graph by recursively deleting leaves or free rays. (We shall do this more formally in the course of the proof of Lemma 2.)

We shall need the following constructive analogue of this pruning lemma. Let T_{0} denote the 2-element set containing the one-vertex tree and the ray. For every ordinal μ > 0, let T_{μ} denote the set of all trees T (with root r, say) such that, for either R := { r } or R some ray in T starting at r, each component of T − R lies in some T_{λ} with λ < μ. Note that T_{λ} ⊆ T_{μ} whenever λ < μ.

Lemma 2. Let T be a tree. There exists an ordinal μ with T ^{∈} T_{μ} if and only if T_{2} ⋠ T.

Proof. For the forward implication, we show by induction on μ that no tree in any T_{μ} contains a subdivision of T_{2}. This is certainly true for μ = 0. Now let μ > 0 and T ^{∈} T_{μ} be given, with root r say, and let R ⊆ T be as in the definition of T_{μ}. (Thus, either R = { r } or R is a ray in T starting at r.) Since deleting a ray from a subdivided T_{2} leaves infinitely many components each containing another subdivided T_{2}, and no tree in any T_{λ} with λ < μ contains a subdivided T_{2} (by the induction hypothesis), we also have T ⋡ T_{2} as required.

For the backward implication, let T ⋡ T_{2} be given, and let r be its root. As mentioned earlier, T can be pruned down to ∅ by deleting leaves or free rays recursively. Indeed, let T_{0} := T, and for every ordinal μ > 0 let T_{μ} be obtained from the tree T_{μ}^{−} := ⋂_{λ<μ} T_{λ} by deleting a leaf or a free ray; if T_{μ}^{−} has neither a leaf nor a free ray, we put T_{μ} := T_{μ}^{−}. Moreover, we label every vertex t ^{∈} T_{μ}^{−} deleted in the definition of T_{μ} with the ordinal μ =: μ_{t}. Now let μ^{∗} be minimal such that T_{μ^{∗}} = T_{μ^{∗}}^{−}, and put T_{μ^{∗}} =: T^{∗}. Note that since T^{∗} has neither leaves nor free rays, any vertex of T^{∗} lies below a vertex with two distinct upper neighbours, in which case we may construct a subdivided T_{2} ⊆ T^{∗} inductively. Thus T^{∗} = ∅, and every vertex t of T now has an ordinal label μ_{t} < μ^{∗}.

Our aim is to show that T ^{∈} T_{μ_{r}}. To this end, we prove the following assertion for every ordinal μ, by induction on μ:

For every t ^{∈} T with μ_{t} = μ, all the vertices t′ ^{∈} T^{t} have labels μ_{t′} ⩽ μ_{t}, and T^{t} ^{∈} T_{μ_{t}}. (∗)

For t = r this yields the desired result.

Let μ and a vertex t ^{∈} T with μ_{t} = μ be given. Since no vertex of T is labelled zero, we have μ > 0. Let R be the subgraph of T induced by all the vertices labelled μ. Then either R = { t } and t is a leaf in T_{μ}^{−}, or R is a free ray in T_{μ}^{−} containing t; in the latter case, R has a tail in T^{t}. In either case T^{t} ∩ T_{μ}^{−} ⊆ R, so any vertex in T^{t} − R has a label λ < μ. This proves the first assertion in (∗), and moreover the root t′ of any component T′ of T^{t} − R has a label λ < μ. Since R ∩ T^{t} is closed downwards in T^{t}, the components of T^{t} − R are closed upwards. Thus T′ = T^{t′}, and the induction hypothesis for (∗) implies that T′ ^{∈} T_{λ}. Hence T^{t} ^{∈} T_{μ}, by the definition of T_{μ} applied with { t } or the ray tR. This completes the proof of (∗), and hence of the lemma. □

For our proof of Halin’s conjecture, we want to show that for every graph G ⋡ T_{2} there is an ordinal τ such that G /^{∈} Γ_{τ}. By Theorem 1, G has a certain tree-decomposition (T, (V_{t})_{t^{∈}T}) with T ⋡ T_{2}, and Lemma 2 tells us that T ^{∈} T_{μ} for some ordinal μ. We now complete the proof of the conjecture by showing that τ exists, even as a function of μ (i.e. independently of G).

Given an ordinal μ, let us write μ =: μ′ + n with μ′ a limit ordinal and n < ω, and define τ(μ) := μ′ + 2n + 2.

Lemma 3. Let G ⋡ T_{2} be a graph with a tree-decomposition (T, (V_{t})_{t^{∈}T}) as in Theorem 1, and let μ be an ordinal such that T ^{∈} T_{μ}. Then G /^{∈} Γ_{τ(μ)}.

Proof. We apply induction on μ. For μ = 0, the tree T is either trivial or a ray. If |T | = 1 then G is finite and hence not even in Γ_{1}. So assume that T is a ray, T = t_{0}t_{1} … say. Since every V_{t} is finite, any infinite subgraph H of G meets V_{t_{i}} for infinitely many i. If H is connected, it therefore even meets every V_{t_{i}} with large enough i. Now if k is the integer associated with the ray t_{0}t_{1} … in Theorem 1, this can happen for no more than k disjoint connected graphs H. Hence G /^{∈} Γ_{2}, as required.

Suppose now that μ > 0. Let r be the root of T. Since T ^{∈} T_{μ} there is an R ⊆ T, where either R = { r } or R is a ray starting at r, such that every component T′ of T − R is a tree in T_{λ} for some λ < μ.

Suppose, for a contradiction, that G ^{∈} Γ_{μ′+2n+2}, and let H_{1}, H_{2}, … be infinitely many disjoint connected subgraphs of G in Γ_{μ′+2n+1}. As in the case of μ = 0, only finitely many of the H_{i} meet V_{t} for infinitely many t ^{∈} R. Let H be one of the other H_{i}, and let U be the (finite) union of those V_{t} with t ^{∈} R that meet H. Since H ^{∈} Γ_{μ′+2n+1}, there are infinitely many disjoint connected graphs H′_{1}, H′_{2}, … ⊆ H in Γ_{μ′+2n}. As U meets only finitely many of these, one of them, H′ say, avoids U and hence lies in a subgraph G′ of G such that

V (G′) = ⋃_{t^{∈}T′} V_{t}

for some component T′ of T − R. Then T′ ^{∈} T_{λ} for some λ < μ, and (T′, (V_{t} ∩ V (H))_{t^{∈}T′}) is a tree-decomposition of H′ as in Theorem 1. Our induction hypothesis therefore implies that H′ /^{∈} Γ_{τ(λ)}. Since λ < μ = μ′ + n, however, clearly

τ(λ) ⩽ μ′ + 2n .

This contradicts the fact that H′ ^{∈} Γ_{μ′+2n} by definition of H′. □

References

1. R. Diestel, Graph Theory (2nd edition), Springer-Verlag 2000.

http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/download.html 2. R. Halin, Miscellaneous problems on infinite graphs, J. Graph Theory (to appear).

3. P.D. Seymour and R. Thomas, Excluding infinite trees, Trans. Amer. Math. Soc. 335 (1994), 597–630.

Reinhard Diestel Mathematisches Seminar der Universität Hamburg Bundesstraße 55 20146 Hamburg Germany

diestel@math.uni-hamburg.de