Decompositions of Infinite Graphs into Small Induced Subgraphs

Reinhard Diestel, Cambridge

We investigate simplicial and related decompositions of infinite graphs into induced subgraphs of strictly lesser cardinality. Such decompositions may be useful for extending results on graphs of bounded order to larger graphs, e.g. results on countable graphs to uncountable ones.

Introduction

In this paper we study decompositions of infinite graphs into induced subgraphs of cardinality strictly less than that of the decomposed graph. Most of the decompositions we consider are simplicial decompositions, a concept first introduced for the study of infinite graphs by Halin [ 3 ]. Simplicial decompositions have since become one of the main tools in infinite graph theory.

The results proved in the first two sections are largely sharpenings of known results due to Halin. In Section 3 we look at another concept introduced by Halin, the a-closure of a graph. The idea behind this concept is slightly to alter a given graph which is itself unsuitable for simplicial decomposition, to decompose the graph thus obtained by one of the standard decomposition theorems, and then to transfer this decomposition back to the original graph.

The tools developed in the first three sections are used in Section 4 to prove our main result, Theorem 4.2. It is a decomposition theorem of a fairly general form, which should make it applicable elsewhere. An immediate corollary of Theorem 4.2 forms the basis for a partial solution to the well-known end-faithful spanning tree problem, given in [ 2 ].

Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family F = (B_{λ})_{λ<σ} is called a simplicial decomposition of G if the following three conditions hold: (S1) G = ⋃_{λ<σ} B_{λ}; (S2) (⋃_{λ<μ} B_{λ}) ∩ B_{μ} =: S_{μ} is a complete graph for each μ (0 < μ < σ); (S3) no S_{μ} contains B_{μ} or any other B_{λ} (0 ≤ λ < μ < σ).

If F = (B_{λ})_{λ<σ} is any fixed family of induced subgraphs of G satisfying (S1), and if H ⊂ G and v ^{∈} V (G), we denote by λ(v) the minimal λ < σ for which v ^{∈} B_{λ}, and set Λ(H) := { λ(v) | v ^{∈} V (H) }. Then λ(v) = μ if and only if v ^{∈} B_{μ}\S_{μ}, and λ(v) < μ for all v ^{∈} S_{μ}. For μ ≤ σ, we write G|_{μ} := ⋃_{λ<μ} B_{λ}.

If F satisfies (S1) and (S2), e.g. if F is a simplicial decomposition, then every G|_{μ} is an induced subgraph of G; for if x, y ^{∈} V (G|_{μ}), xy ^{∈} E(G)\E(G|_{μ}), and τ < σ is minimal with xy ^{∈} E(B_{τ}) (τ exists by (S1)), then xy must already be an edge of G|_{τ} (by (S2) and μ ≤ τ), contrary to the choice of τ.

We shall usually refer to a complete graph as a simplex, and call the graphs S_{μ} = G|_{μ} ∩ B_{μ} in (S2) the simplices of attachment in F.

F is called coherent if, for each λ < σ, B_{λ}\S_{λ} is connected and every vertex of S_{λ} has a neighbour in B_{λ}\S_{λ}.

H ⊂ G is attached to H′ ⊂ G\H if every vertex of H is adjacent to a vertex in H′. Thus, if F is coherent, then each S_{λ} is attached to B_{λ}\S_{λ}. More generally we shall say that H is attached (in G) if H is attached to some component of G\H; otherwise H is unattached (in G). One of the basic properties of factors in simplicial decompositions is that they are unattached subgraphs [ 1 ].

For X, Y ⊂ G, we call a path P ⊂ G an X–Y path if its endvertices are in X and Y, respectively, and its interior P̊ lies in G \ (X ∪ Y). Moreover, we write G [ X → Y ] for the subgraph of G induced by all vertices of G that can be reached from X by a path whose interior avoids Y. More precisely, G [ X → Y ] is the subgraph of G induced by all vertices v ^{∈} G for which G contains a path x_{1} … x_{n} satisfying x_{1} ^{∈} X, x_{n} = v, and x_{i} ^{∈} Y ⇒ i = n. When the underlying graph G is fixed, we shall usally abbreviate G [ X → Y ] ∩ Y to Y [ X]. Thus, Y [ X] is the subgraph of Y induced by all terminal vertices of X–Y paths in G.

Notice that for Y = G this definition coincides with the conventional meaning of G [ X], denoting the subgraph of G induced by the vertices of X.

Another frequent example for the use of this notation is the following. If H is an induced subgraph of G and C is a component of G\H, then H [ C] is spanned by all those vertices of H that have a neighbour in C. Then H = H [ C] if and only if H is attached to C in G.

Two paths are independent if their interiors are disjoint. The Menger number μ_{G}(x, y) of two vertices x, y ^{∈} G is the maximum of all cardinals a for which there exists a set P(x, y) of pairwise independent x–y paths in G with |P(x, y)| = a. To see that this maximum exists, let P(x, y) be an inclusion-maximal set of independent x–y paths in G (by Zorn’s lemma). Suppose first that P(x, y) is finite, say | ⋃ P(x, y)| = n. Then no set of independent x–y paths in G can contain more than n paths, since otherwise one of these paths avoids P̊ for all P ^{∈} P(x, y) and could be added to P(x, y). If P(x, y) is infinite on the other hand, then, for the same reason, |P(x, y)| = | ⋃ P(x, y)| is the maximum cardinality of any set of pairwise independent x–y paths in G.

Let H and X be graphs. In analogy to the familiar notation of TX for subdivisions of X (or ‘topological’ X graphs) we say that H is an HX (H for ‘homomorphism’) if its vertex set V (H) admits a partition { V_{x} | x ^{∈} V (X) } into subsets V_{x} spanning connected subgraphs in H, such that H contains a V_{x}–V_{y} edge if and only if x and y are adjacent in X.

1. Convex subgraphs

A graph H ⊂ G is convex in G if H contains every induced path in G whose endvertices are in H.

Proposition 1.1. For H ⊂ G, the following statements are equivalent.

(i) H is convex in G.

(ii) The endvertices of every H–H path in G are adjacent in H. (iii) H is an induced subgraph of G, and for every x ^{∈} G\H, H [ x] = G [ x → H] ∩ H

is a simplex. (iv) If T ⊂ V (H) and U, W ⊂ V (H)\T, then T separates U from W in H if and only if

T separates U from W in G. □

We remark that if H is convex in G and H′ ⊂ H, then H′ is convex in H if and only if H′ is convex in G. Also, if H ⊂ G is the nested union of a well-ordered family (H_{λ})_{λ<μ} of convex subgraphs of G (i.e., if H = ⋃_{λ<μ} H_{λ} and H_{λ′} ⊂ H_{λ} for λ′ < λ < μ), then H is again convex in G.

Lemma 1.2. Let G be a graph, with subgraphs G_{1} and G_{2}. Suppose that S := G_{1} ∩ G_{2} is a simplex which separates G_{1}\S from G_{2}\S in G, and that G_{i} is convex in G [ G_{i} → S], i = 1, 2. Then G_{1} ∪ G_{2} is a convex subgraph of G.

Proof. Since S is a simplex, G [ G_{i} → S] is convex in G. Therefore G_{i} is convex in G, because G_{i} is convex in G [ G_{i} → S]. Let P = x … y be an induced path in G with x, y ^{∈} G_{1} ∪ G_{2}; assume without loss of generality that x ^{∈} G_{1}. We have to show that P ⊂ G_{1} ∪ G_{2}. If y ^{∈} G_{1}, this follows from the convexity of G_{1} in G. If y /^{∈} G_{1}, then P has a vertex s in S. Then P_{x,s} ⊂ G_{1} and P_{s,y} ⊂ G_{2}, by the convexity of G_{1} and G_{2} in G, respectively. Hence P ⊂ G_{1} ∪ G_{2}, as claimed. □

Convexity is perhaps the most fundamental concept in the study of simplicial decompositions, due to the following fact:

Proposition 1.3. [ 1 ] If (B_{λ})_{λ<σ} is a simplicial decomposition of G, then every B_{μ} and every G|_{μ} is convex in G.

Proof. Let P ⊂ G be an induced path in G with endvertices x, y ^{∈} G|_{μ}. We have to show that P ⊂ G|_{μ}. Since P is finite, Λ(P) has a maximum λ^{∗}; let v ^{∈} P be such that λ(v) = λ^{∗}. Since G|_{λ^{∗}+1} is an induced subgraph of G, we have P ⊂ G|_{λ^{∗}+1}. Suppose λ^{∗} ≥ μ. Then x, y ^{∈} G|_{λ^{∗}}, while v ^{∈} B_{λ^{∗}}\S_{λ^{∗}}. Since S_{λ^{∗}} = B_{λ^{∗}} ∩ G|_{λ^{∗}}, S_{λ^{∗}} separates B_{λ^{∗}}\S_{λ^{∗}} from G|_{λ^{∗}}\S_{λ^{∗}} in G|_{λ^{∗}+1}. Therefore each of the paths P_{x,v} and P_{v,y} meets S_{λ^{∗}}, so P has at least 2 vertices s, s′ in S_{λ^{∗}}. The edge ss′ is a chord of P, contradicting its choice as an induced subgraph. Hence λ^{∗} < μ, giving P ⊂ G|_{λ^{∗}+1} ⊂ G|_{μ} as claimed.

Similarly if x, y ^{∈} B_{μ}, then any induced x–y path P ⊂ G is contained in G|_{μ+1}, by the convexity of G|_{μ+1} in G. Moreover, P cannot meet G|_{μ}\S_{μ}, because then P would have two non-consecutive vertices in S_{μ}. Hence P ⊂ B_{μ}, so B_{μ} is convex in G. □

The following result is due to Halin [ 4 ]. We include its short proof for the convenience of the reader.

Lemma 1.4. [ 4 ] Let G be a graph, a > ℵ_{0} a regular cardinal, and suppose that μ_{G}(x, y) < a for any two non-adjacent vertices x, y of G. Then, for every X ⊂ G with |X| < a, there exists a convex subgraph H of G such that X ⊂ H and |H| < a.

Proof. We construct a sequence of subgraphs H_{0} ⊂ H_{1} ⊂ … of G, where H_{0} = X and each H_{n} has order < a. Suppose that H_{0}, …, H_{n} have been defined as stated. For each pair x, y of non-adjacent vertices of H_{n} choose an inclusion-maximal set P_{n}(x, y) of independent H_{n}–H_{n} paths in G with endvertices x, y (using Zorn’s Lemma). Since μ_{G}(x, y) < a by assumption, we have |P_{n}(x, y)| < a for every pair x, y. Then

H_{n+1} := H_{n} ∪ ⋃_{x,y^{∈}H_{n}} ⋃ P_{n}(x, y)

has order < a, because |H_{n}|^{2} < a and a is regular.

Let H := ⋃_{n=0}^{∞} H_{n}. Clearly |H| < a, since ℵ_{0} < a by assumption. We use Proposition 1.1.(ii) to show that H is convex in G. Suppose P = x … y ⊂ G is an H–H path, and xy /^{∈} E(H). Let n ^{∈} ℕ be such that x, y ^{∈} H_{n}. Then P_{n}(x, y) ∪ { P } is a set of H_{n}–H_{n} paths which contradicts the assumed maximality of P_{n}(x, y). □

Lemma 1.4 will essentially be our standard tool in the construction of simplicial decompositions for choosing their factors; recall that such factors are always convex subgraphs. Yet simplicial factors are not only convex but also unattached. The convex graphs H provided by Lemma 1.4, however, may well be attached in G: consider, for example, the case where G is a simplex of order a and H is a proper subsimplex of G.

In order to sharpen Lemma 1.4 in such a way that it guarantees the existence of small convex and unattached supergraphs, we therefore have to ban large complete subgraphs:

Lemma 1.5. Let G be a graph, a > ℵ_{0} a regular cardinal, and suppose that μ_{G}(x, y) < a for any two non-adjacent vertices x, y of G. Suppose further that G has no complete subgraph of order a. Then, for every X ⊂ G with |X| < a, there exists a convex and unattached subgraph H of G such that X ⊂ H and |H| < a.

Proof. By Lemma 1.4, G has a convex subgraph H′ of order < a that contains X. Suppose H′ is attached in G. Then H′ is a simplex, by Proposition 1.1.(iii). Let X′ ⊂ G be a maximal simplex containing H′; then |X′| < a by assumption. If X′ = G, then H := X′ is as desired. Otherwise pick v ^{∈} V (G)\V (X′), and let H be a convex subgraph of G containing X′ and v (again by Lemma 1.4). H is unattached in G, because otherwise H would be a simplex contradicting the maximality of X′. □

2. The basic decomposition theorem

The following theorem is again a sharpened version of a result of Halin [ 5,6 ].

Theorem 2.1. Let G be a graph and a a regular cardinal, such that |G| ≥ a > ℵ_{0}. Suppose that G ⊅ K_{a}, and that μ_{G}(x, y) < a for any two non-adjacent vertices x, y of G. Let σ be the initial ordinal of |G|. Then G admits a coherent simplicial decomposition F = (B_{λ})_{λ<σ} with |B_{λ}| < a for all λ < σ.

Proof. Let V (G) be well-ordered as (v_{ρ})_{ρ<σ}. We define the factors B_{λ} of F inductively for λ < σ, so that the following two conditions are satisfied for each λ:

(i) B_{λ} is unattached in G, and |B_{λ}| < a; (ii) ⋃_{λ′≤λ} B_{λ′} is convex in G. Let μ be given, 0 ≤ μ < σ, and suppose that for every λ < μ we have defined B_{λ} so as to satisfy (i) and (ii). We shall define B_{μ} in such a way that (i) and (ii) hold for λ = μ.

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

Since |G|_{μ}| < a by (i) and the regularity of a, we have G\G|_{μ} ≠ ∅. Let ρ(μ) := min { ρ | v_{ρ} /^{∈} G|_{μ} }, and put

\begin{aligned}G_{μ} & := G [ v_{ρ(μ)} → G|_{μ}] , \\ C_{μ} & := G_{μ} \ G|_{μ} , \\ S_{μ} & := G_{μ} ∩ G|_{μ} . \end{aligned}

Then S_{μ} = G|_{μ} [ v_{ρ(μ)} ], so S_{μ} is a simplex (Proposition 1.1.(iii)) and hence of order < a.

Applying Lemma 1.5 to the graph G_{μ}, we define B_{μ} to be the convex and unattached subgraph H of G_{μ} that contains S_{μ} ∪ { v_{ρ(μ)} }. Then |B_{μ}| < a, and (i) holds for λ = μ. Furthermore, S_{μ} = G|_{μ} ∩ B_{μ}, as required by (S2). By Lemma 1.2, G|_{μ} ∪ B_{μ} is convex in G, giving (ii) for λ = μ. Finally, as S_{μ} is attached, it cannot contain any factor B_{λ} for λ < μ, since these are unattached by assumption (i). Therefore our choice of B_{μ} satisfies (S3).

It remains to show that ⋃_{λ<σ} B_{λ} ⊃ G (S1), and that F is coherent. To see (S1), notice that v_{λ} ^{∈} G|_{λ+1} for every λ < σ, which follows by our choice of B_{λ} and an easy induction on λ. Thus

V (G) ⊂ ⋃_{λ<σ} V (G|_{λ+1}) = ⋃_{λ<σ} V (B_{λ}) .

As every G|_{λ+1} is convex and hence induced in G, this implies (S1).

To see that F is coherent, suppose that, for some λ < σ, S_{λ} is not attached to B_{λ}\S_{λ} or B_{λ}\S_{λ} is disconnected. In either case there exists a subsimplex S ⊂ S_{λ} which separates vertices x, y ^{∈} B_{λ}\S in B_{λ}. As S_{λ} is attached to C_{λ} and B_{λ}\S_{λ} ⊂ C_{λ}, S cannot separate x and y in G_{λ}. This contradicts the convexity of B_{λ} in G_{λ}, by Proposition 1.1.(iv). □

3. The a-closure of a graph

The reader will have noticed that the applicability of Theorem 2.1 is likely to be hindered by an obvious shortcoming: its condition on the Menger number μ_{G}(x, y) for non-adjacent vertices x, y. In this section we study a rather ingenious idea, due to Halin, for adapting graphs to this condition that would otherwise fail to meet it.

Given a graph G and an ordinal a, let the a-closure [ G]_{a} of G be the graph with vertex set V (G) and edge set E(G) ∪ { xy | μ_{G}(x, y) ≥ a }. The term ‘a-closure’ is justified by the following observation:

Proposition 3.1. If G is a graph and a is an infinite cardinal, then [ G]_{a} is its own a-closure.

Proof. Put G′ := [ G]_{a}, and let G′′ be the a-closure of G′. Suppose G′′ ≠ G′. Then there exist vertices x, y ^{∈} G such that xy ^{∈} E(G′′) but xy /^{∈} E(G′). Let P be a maximal set of independent x–y paths in G; as xy /^{∈} E(G′), |P| < a. Let X := ⋃ { P̊ | P ^{∈} P }. Then |X| < a, and X separates x from y in G. Since xy ^{∈} E(G′′)\E(G′), there exists a set P′ of at least a independent x–y paths in G′, so one of these paths, P′ say, avoids X. Thus P′ contains an edge x′y′ for which x′ and y′ belong to different components of G\X. But as x′y′ ^{∈} E(G′)\E(G), there exist a independent x′–y′ paths in G. One of these paths must avoid X, contradicting the fact that X separates x′ and y′ in G. □

It is clear that if a is a regular uncountable cardinal and G is a graph of order ≥ a, then the a-closure [ G]_{a} of G is such that μ_{[ G]_{a}}(x, y) < a for any two non-adjacent vertices x and y. We can therefore apply Theorem 2.1 to [ G]_{a} as soon as we know that [ G]_{a} meets the other condition in Theorem 2.1, the condition of not containing a K_{a}. The next question is therefore how this can be ensured by imposing an additional condition on G.

The following proposition, which extends results of Halin [ 5 ] [ 6 ], implies that if G contains no subdivided K_{a} then [ G]_{a} ⊅ K_{a}—which seems a tolerable strengthening of the original requirement that G ⊅ K_{a}. In fact, we can prove something more general than this:

Proposition 3.2. If X is a graph and a is an infinite cardinal such that |X| ≤ a, then the following equivalences hold for every graph G:

\begin{aligned}G ⊃ TX & ⇔ [ G]_{a} ⊃ TX \\ G ⊃ HX & ⇔ [ G]_{a} ⊃ HX . \end{aligned}

Proof. If |G| < a, then [ G]_{a} = G and the assertions are trivial. We shall therefore assume that |G| ≥ a. Suppose that [ G]_{a} ⊃ TX (or [ G]_{a} ⊃ HX). Let X′ ⊂ [ G]_{a} be a TX (an HX, respectively), without loss of generality such that X′ is finite if X is, and otherwise |X′| = |X|. We show that G ⊃ TX′, which implies both assertions.

Let E := E(X′) ∪ U, where U is the set of isolated vertices of X′. Then |E| = |X′| or E is finite, so |E| ≤ a. Let β be the initial ordinal of |E|. Pick a well-ordering (e_{γ})_{γ<β} of E. For all γ < β, choose paths P_{γ} ⊂ G as follows. Let γ < β be given, and suppose that P_{δ} has been defined for all δ < γ. Put X_{γ} := ⋃_{δ<γ} P_{δ}. Then |X_{γ}| < a: trivially if γ is finite, and otherwise because |X_{γ}| ≤ |γ| < |E| ≤ a by choice of β. Now if e_{γ} ^{∈} U, let P_{γ} be any vertex of G that is not in X_{γ}. Such a vertex exists, because |G| ≥ a by assumption. On the other hand if e_{γ} ^{∈} E(X′), say e_{γ} = xy, let P_{γ} be an x–y path in G whose interior avoids X_{γ}. Such P_{γ} exists, because either e_{γ} is itself in E(G), or G contains ≥ a independent x–y paths. Finally, let X′′ := ⋃_{γ<β} P_{γ}. Then G ⊃ X′′ = TX′, as desired. □

The decomposition whose existence is asserted in Theorem 2.1 has two main features: the fact that its factors are small, and the fact that it is a simplicial decomposition, i.e., that all its attachment graphs are complete. The first of these features, the size of the factors, is clearly not affected when we later delete some edges of the graph. Thus in order to decompose a given graph G into factors of order < a, we may employ Theorem 2.1 to decompose its a-closure [ G]_{a}, and then use the induced decomposition of G.

To make this precise, let us define a new kind of decomposition, in which (S2) is replaced with a condition on the order of the attachment graphs. Given an infinite cardinal a and a graph G, call a family (B_{λ})_{λ<σ} of induced subgraphs of G an a-decomposition of G if it satisfies (S1), (S3) and

(S_{a}2) Each subgraph (⋃_{λ<μ} B_{λ}) ∩ B_{μ} =: S_{μ} has order < a (0 < μ < σ),

(S_{a}5) Every graph ⋃_{λ<μ} B_{λ} is an induced subgraph of G (0 < μ < σ).

We then have the following result:

Theorem 3.3. If G is a graph, a is a regular uncountable cardinal and G ⊅ TK_{a}, then G has an a-decomposition (B_{λ})_{λ<σ} into factors of order < a. This decomposition can be chosen in such a way that, for every μ < σ, S_{μ} separates (⋃_{λ<μ} B_{λ}) \ S_{μ} from B_{μ}\S_{μ} in G.

Proof. By Proposition 3.2, the a-closure [ G]_{a} =: G′ of G has no subgraph isomorphic to K_{a}, and μ_{G′}(x, y) < a for non-adjacent x, y ^{∈} G′ by Proposition 3.1. By Theorem 2.1 therefore, G′ admits a simplicial decomposition F′ = (B′_{λ})_{λ<σ} with |B′_{λ}| < a for all λ < σ. Then F = (B_{λ})_{λ<σ} is an a-decomposition of G, where B_{λ} := B′_{λ} ∩ G.

By definition, V (S_{μ}) separates (B′_{μ})\V (S_{μ}) from V (G′|_{μ})\V (S_{μ}) in G′|_{μ+1}. As G′|_{μ+1} is convex in G′ (Proposition 1.3), V (S_{μ}) separates the same vertices in G′, and hence also in G. □

4. The main result

By placing the emphasis in Theorem 3.3 just on the size of the factors B′_{μ}, we lose some possibly valuable information on G′ = [ G]_{a} (see the proof of Theorem 3.3) which might still be exploited for G: the fact that the endvertices of any edge in E(G′)\E(G) are joined in G by at least a independent paths. For example, we might be trying to prove that G has a subgraph with a certain property P, and it is easier to find such a subgraph H in G′. Now if P is invariant under subdivision, i.e. under the replacement of edges with independent paths, we may be able to transform H back into a subgraph of G still satisfying P, by replacing the foreign edges with suitable paths in G. The fact that for each edge there are ≥ a paths to choose from helps to select them in such a way that they are pairwise disjoint and avoid the rest of H. To keep the proofs lucid, it is generally best to keep the interiors of different replacement paths as far from each other as possible, for example in distinct components of subgraphs G\G|_{μ}, or inside different factors.

Our last lemma and theorem follow up this line. Theorem 4.2 is the main result of this paper, and an immediate corollary of it, Corollary 4.3, is the key tool for a major theorem on the existence of end-faithful spanning trees in infinite graphs [ 2 ].

Lemma 4.1. Let a and b be regular cardinals with a > b ≥ ℵ_{0}. Let G be a graph not containing any complete subgraph of order b, and such that μ_{G}(x, y) < a for any two nonadjacent vertices x, y of G. Let further E ⊂ E(G). Then every graph X ⊂ G of order < a has a convex and unattached supergraph H in G, |H| < a, which satisfies the following condition: (∗) For every two vertices x, y of H, the number of components C of G\H for which

G [ C → H] contains an H–H path P with endvertices x, y and E(P) ⊂ E, is either 0 or at least a.

Proof. Let β be the initial ordinal of b. For every λ ≤ β we shall define a convex and unattached supergraph H_{λ} of X, such that |H_{λ}| < a for all λ ≤ β, and H_{λ} ⊂ H_{μ} whenever λ < μ ≤ β. H_{β} will be our desired graph H.

Let H_{0} be the convex and unattached supergraph of X provided by Lemma 1.5. Suppose that H_{λ} has been defined as stated for every λ < μ, where μ ≤ β. If μ is a limit ordinal, we set H_{μ} := ⋃_{λ<μ} H_{λ}; then H_{μ} is convex in G because every H_{λ} is convex, H_{μ} is unattached because H_{μ} ⊃ H_{0} and H_{0} is unattached, and |H_{μ}| < a, because |H_{λ}| < a for every λ < μ and |μ| ≤ |β| = b < a.

Suppose now that μ is a successor ordinal, say of λ. For distinct vertices x, y of H_{λ}, let C_{λ}(x, y) denote the set of all components C of G\H_{λ} that are relevant for condition (∗)— i.e., for which G [ C →H_{λ}] contains an H_{λ}–H_{λ} path P with endvertices x, y and E(P) ⊂ E. Let E_{λ} be the set of all pairs { x, y } of vertices of H_{λ}, for which C_{λ}(x, y) is non-empty but of order < a. Notice that since H_{λ} is convex, any graph of the form H_{λ} [ C], where C is a component of G\H_{λ}, must be a simplex, and hence of order < b. Thus E_{λ} ⊂ E(H_{λ}), and for every xy ^{∈} E_{λ} and each C ^{∈} C_{λ}(x, y), Lemma 1.4 provides us with a convex subgraph H_{λ}(C) ⊂ G [ C → H_{λ}] of order < a, so that H_{λ}(C) contains H_{λ} [ C] and at least one vertex of C.

Set

H_{μ} := H_{λ} ∪ ⋃_{xy^{∈}E_{λ}} ⋃_{C^{∈}C_{λ}(x,y)} H_{λ}(C) .

H_{μ} is convex in G, because H_{λ} and every H_{λ}(C) is convex, and H_{λ} [ C] = H_{λ} ∩ H_{λ}(C) is a simplex which separates H_{λ} \ H_{λ} [ C] from H_{λ}(C) \ H_{λ} [ C] in G (see Lemma 1.2). H_{μ} is unattached in G, because H_{μ} ⊃ H_{0} and H_{0} is unattached. Finally, |H_{μ}| < a, because |E_{λ}| ≤ |H_{λ}|^{2} < a, |C_{λ}(x, y)| < a for xy ^{∈} E_{λ}, and |H_{λ}(C)| < a for C ^{∈} C_{λ}(x, y).

Let us finally set H := H_{β}.

It remains to prove that H satisfies (∗). Suppose (∗) fails, and let x, y ^{∈} H be such that 1 ≤ |C_{β}(x, y)| < a. Pick C ^{∈} C_{β}(x, y). We shall prove that C ^{∈} C_{γ}(x, y) for some γ < β, deduce that |C_{γ}(x, y)| ≥ a (as otherwise H_{γ+1} ought to contain a vertex from C), and use this to derive a contradiction to the fact that |C_{β}(x, y)| < a and |H| < a.

Let S := H [ C]. Clearly x, y ^{∈} S. For vertices s ^{∈} S, write λ(s) := min { λ | s ^{∈} H_{λ} }, and put Λ := { λ(s) | s ^{∈} S }. As β is the initial ordinal of b and hence a limit ordinal, we have λ(s) < β for every s ^{∈} S, and therefore |λ| < b for every λ ^{∈} Λ. Moreover, |Λ| ≤ |S| < b, because S is a simplex. Therefore γ := ⋃ Λ < β (by the regularity of b), and S ⊂ H_{γ}.

We now show that C ^{∈} C_{γ}(x, y). Clearly C ⊂ G\H ⊂ G\H_{γ}; let C′ be the component of G\H_{γ} containing C. Then C′ ^{∈} C_{γ}(x, y), so all we have to show is that C′\C = ∅. But if C′\C ≠ ∅, then G contains a C–(C′\C) edge, because C′ is connected. Therefore (C′\C) ∩ H [ C] ≠ ∅, which contradicts the fact that H [ C] = S ⊂ H_{γ}. Thus C′\C = ∅, as required.

To show that |C_{γ}(x, y)| ≥ a, recall that if |C_{γ}(x, y)| < a, then xy ^{∈} E_{γ}, and consequently H_{γ+1} ∩ C ≠ ∅. But then also H ∩ C ≠ ∅, a contradiction. Now as |C_{γ}(x, y)| ≥ a but |C_{β}(x, y)| < a, we have |C_{γ}(x, y) \ C_{β}(x, y)| ≥ a, while H ∩ C_{γ} ≠ ∅ for every C_{γ} ^{∈} C_{γ}(x, y) \ C_{β}(x, y). This contradicts the fact that |H| < a. □

Theorem 4.2. Let a and b be regular cardinals with a > b ≥ ℵ_{0}, and let G be a graph of order ≥ a which does not contain any TK_{b}. Let σ be the initial ordinal of |G|. Then the a-closure [ G]_{a} =: G′ of G admits a coherent simplicial decomposition F = (B_{λ})_{λ<σ} into factors of order < a and with simplices of attachment of order < b, which has the following property: for every μ < σ and every edge xy ^{∈} E_{μ} := (E(B_{μ})\E(S_{μ})) \ E(G), there are at least a ordinals ν, with S_{ν} ⊂ B_{μ}, such that B_{ν} contains an S_{ν}–S_{ν} path P with endvertices x, y and E(P) ⊂ E(G).

Proof. Our proof is along the lines of that of Theorem 2.1; the main difference will be that we use Lemma 4.1 rather than Lemma 1.5 to choose the factors for F, and that our choice of the graph X in the lemma has to ensure that each factor B_{ν} contains the correct S_{ν}–S_{ν} paths. For the application of Lemma 4.1, note that G′ ⊅ K_{b} by Proposition 3.2, and that μ_{G′}(x, y) < a for non-adjacent x, y ^{∈} G′ by definition of G′.

Let V (G′) be well-ordered as (v_{ρ})_{ρ<σ}. In our construction of F, we shall use the following abbreviations:

\begin{aligned}G′|_{λ} & := ⋃_{λ′<λ} B_{λ′} \\ E_{λ} & := (E(B_{λ})\E(G′|_{λ})) \ E(G) . \end{aligned}

Let μ be given, 0 ≤ μ < σ. Suppose that for every λ < μ we have already defined an induced subgraph B_{λ} of G′ and, for all xy ^{∈} E_{λ}, sets P(xy) of G′|_{λ+1}–G′|_{λ+1} paths P ⊂ G with endvertices x, y, such that

(i) B_{λ} is unattached in G′; (ii) G′|_{λ+1} is convex in G′; (iii) if C is a component of G′ \ G′|_{λ+1} and e ^{∈} E_{λ}, then at most one P ^{∈} P(e) meets C. We shall define B_{μ} and P(e) (for all e ^{∈} E_{μ}) such that (i)–(iii) hold for λ = μ.

Notice first that G′|_{μ} is convex: trivially if μ = 0, by assumption if μ is a successor ordinal, and by G′|_{μ} = ⋃_{λ<μ} G′|_{λ+1} and (ii) if μ is a limit ordinal.

Let ρ(μ) := min { ρ | ν_{ρ} /^{∈} G′|_{μ} }, and put

\begin{aligned}G′_{μ} & := G′ [ v_{ρ(μ)} → G′|_{μ}] , \\ C_{μ} & := G′_{μ} \ G′|_{μ} , \\ S_{μ} & := G′_{μ} ∩ G′|_{μ} . \end{aligned}

Then S_{μ} = G′|_{μ} [ v_{ρ(μ)} ], so S_{μ} is a simplex (Proposition 1.1.(iii)), and hence of order < b.

Notice that if Λ(S_{μ}) has a maximum λ, then C_{μ} is already a component of G′\G′|_{λ+1} (even if λ + 1 < μ). Then the graph

Q_{μ} := ⋃ { P ^{∈} P(e) | e ^{∈} E_{λ} and P ∩ C_{μ} ≠ ∅ }

has order < a, by (iii) and the fact that |S_{μ}| < a. Applying Lemma 4.1 to the graph G′_{μ}, let B_{μ} be the graph H that extends X ⊂ G′_{μ} with respect to E := E(G′_{μ}) ∩ E(G), where

X := \{ \begin{matrix}S_{μ} ∪ \{ v_{ρ(μ)} \} ∪ Q_{μ}, & if λ = max Λ(S_{μ}); \\ S_{μ} ∪ \{ v_{ρ(μ)} \}, & if Λ(S_{μ}) has no maximum. \end{matrix}

(It is clear that X has order < a.) By Lemma 4.1, |B_{μ}| < a, and B_{μ} is convex and unattached in G′_{μ}. Since B_{μ} [ v] = S_{μ} ⫋ B_{μ} for every v ^{∈} G′\G′_{μ}, B_{μ} is also unattached in G′, establishing (i) for λ = μ. By Lemma 1.1, G′|_{μ+1} = G′|_{μ} ∪ B_{μ} is convex in G′, giving (ii).

Before we define P(e) for e ^{∈} E_{μ} and show (iii) for λ = μ, let us note the following consequence of the fact that S_{μ} separates B_{μ}\S_{μ} from G′|_{μ}\S_{μ} in G′.

Let P = x … y be any B_{μ}–B_{μ} path in G′, and assume that y ^{∈} B_{μ}\S_{μ}. Then y ^{∈} C_{μ} and P̊∩ S_{μ} = ∅, so P̊ ⊂ C_{μ}. Thus P̊ ⊂ G′_{μ}\G′|_{μ+1} and

G′ [ P → G′|_{μ+1} ] = G′ [ P → B_{μ}] = G′_{μ} [ P → B_{μ}]
G′ [ P → G′|_{μ+1} ] ∩ G′|_{μ+1} = G′ [ P → B_{μ}] ∩ B_{μ} = G′_{μ} [ P → B_{μ}] ∩ B_{μ} ,  (1)

and hence

G′ [ P → G′|_{μ+1} ]\G′|_{μ+1} = G′ [ P → B_{μ}]\B_{μ} = G′_{μ} [ P → B_{μ}]\B_{μ}  (2)

(see Fig. 1). Another way of stating (2) is to say that whenever C ⊂ G′ contains the interior of a B_{μ}–B_{μ} path one of whose endvertices is in B_{μ}\S_{μ}, C is a component of G′\G′|_{μ+1} if and only if C is a component of G′\B_{μ}, and if and only if C is a component of G′_{μ}\B_{μ}.

FIGURE 1.

For the definition of P(e), let now e = xy ^{∈} E_{μ} be given. As e /^{∈} E(G′|_{μ}) by definition of E_{μ}, we may assume that y ^{∈} B_{μ}\S_{μ}. Since e ^{∈} E(G′)\E(G) and G′ is the a-closure of G, there exists a set P of at least a independent x–y paths P ⊂ G. Since |B_{μ}| < a, not all of these paths can have a vertex of B_{μ} in their interior, so there exists at least one (in fact, at least a) component(s) C of G′\B_{μ} such that P̊ ⊂ C. Then

C = G′ [ P → B_{μ}]\B_{μ} =_{(2)} G′_{μ} [ P → B_{μ}]\B_{μ}, so C is also a component of G′_{μ}\B_{μ}. By

Lemma 4.1, this implies that there exists a set C of at least a components C′ of G′_{μ}\B_{μ} for which G′_{μ} [ C′ → B_{μ}] contains a B_{μ}–B_{μ} path P′ with endvertices x, y and E(P′) ⊂ E(G), and every such C′ is also a component of G′\G′|_{μ+1} (again by (2)). For each C′ ^{∈} C pick one such path P′, and let P(xy) be the set of all these paths. Clearly |P(xy)| ≥ a, and (iii) holds for λ = μ.

The proof that F = (B_{λ})_{λ<σ} is a coherent simplicial decomposition of G′ is the same as for Theorem 2.1. It thus remains to show that for every μ < σ and every edge xy ^{∈} E_{μ} there are at least a ordinals ν, with S_{ν} ⊂ B_{μ}, such that B_{ν} contains an S_{ν}–S_{ν} path P with endvertices x, y and E(P) ⊂ E(G). Let μ < σ and e = xy ^{∈} E_{μ} be given. By definition of P(e), every P̊ for P ^{∈} P(e) is contained in some component C(P) of G′\G′|_{μ+1}, and these components are distinct for different paths P. Consider any fixed P ^{∈} P(e), and put C(P) =: C and min Λ(C) =: ν. Then C = C_{ν}, so C is still a component of G′\G′|_{ν}. Furthermore,

S_{ν} = G′_{ν} ∩ G′|_{ν}

= G′ [ C → G′|_{ν} ] ∩ G′|_{ν} = G′ [ C → G′|_{μ+1} ] ∩ G′|_{μ+1} = G′ [ P → G′|_{μ+1} ] ∩ G′|_{μ+1}

=_{(1)} G′ [ P → B_{μ}] ∩ B_{μ}

⊂ B_{μ} .

Since C(P) ∩ C(P′) = ∅ for P ≠ P′, the values of ν differ for distinct P ^{∈} P(e). As |P(e)| ≥ a, this completes the proof. □

We finish this paper with a corollary of Theorem 4.2, which plays a central role in the proof of a result on the so-called end-faithful spanning tree problem for infinite graphs [ 2 ].

Let F = (B_{λ})_{λ<σ} be a simplicial decomposition of a graph G. F is called a simplicial tree-decomposition of G if, for every μ < σ, (S4) S_{μ} ⊂ B_{λ} for some λ < μ. It is not difficult to show that a F is a simplicial tree-decomposition if and only if Λ(S_{μ}) is finite for every μ < σ [ 1 ]. Then τ(μ) := max Λ(S_{μ}) is the smallest λ < μ with S_{μ} ⊂ B_{λ}, and the graph T_{F} = T_{F} (G) defined by

\begin{aligned}V (T_{F}) & := \{ B_{λ} | λ < σ \} \\ E(T_{F}) & := \{ B_{μ}B_{τ(μ)} | μ < σ \} \end{aligned}

is a tree.

Corollary 4.3. Let G be an uncountable graph not containing any subdivided infinite simplex. Then the ℵ_{1}-closure G′ of G admits a coherent simplicial tree-decomposition F = (B_{λ})_{λ<σ} into countable factors and with finite simplices of attachment, which has the following property: for every μ < σ and every edge xy ^{∈} (E(B_{μ})\E(S_{μ})) \ E(G), there are uncountably many ordinals ν, with τ(ν) = μ, such that B_{ν} contains an S_{ν}–S_{ν} path P with endvertices x, y and E(P) ⊂ E(G).

Proof. Choose F by Theorem 4.2, putting a := ℵ_{1} and b := ℵ_{0}. As every S_{μ} is finite, F is a simplicial tree-decomposition. The assertion that τ(ν) = μ follows from the fact that S_{ν} ⊂ B_{μ} by Theorem 4.2, while S_{ν} ⊄ S_{μ}, because x, y ^{∈} S_{ν} and xy /^{∈} E(S_{μ}) by assumption. □

References

[ 1 ] R. Diestel, Graph Decompositions—a case study, Oxford University Press, in preparation. [ 2 ] R. Diestel, On end-faithful spanning trees in infinite graphs, submitted. [ 3 ] R. Halin, Simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen, Math. Ann. 156

(1964), 216–225. [ 4 ] R. Halin, Ein Zerlegungssatz für unendliche Graphen und seine Anwendung auf Homomorphiebasen,

Math. Nachr. 33 (1967), 91–105. [ 5 ] R. Halin, Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl, Abh.

Math. Sem. Univ. Hamburg 31 (1967), 156–165. [ 6 ] 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.

Reinhard Diestel, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, England.