SIMPLICIAL MINORS AND DECOMPOSITIONS OF GRAPHS Reinhard Diestel, Cambridge

1. Introduction

The purpose of this paper is to give natural characterizations of the countable graphs that admit tree-decompositions or simplicial tree-decompositions into primes. Tree-decompo-sitions were recently intruduced by Robertson and Seymour in their series of papers on Graph Minors [ 7 ]. Simplicial tree-decompositions were first considered by Halin [ 6 ], being the most typical kind of ‘simplicial decomposition’ as introduced by Halin [ 5 ] in 1964. The problem of determining which infinite graphs admit a simplicial decomposition into primes has stood unresolved since then; a first solution for simplicial tree-decompositions was given in [ 2 ].

Our characterization of the countable graphs admitting a simplicial tree-decomposi-tion into primes is based on the characterization given in [ 2 ]. Similarly to Kuratowski’s well-known theorem on planar graphs, we shall characterize the graphs admitting a prime decomposition by two forbidden minors, the notion of a minor being slightly restricted to match the purpose.

Our second characterization, that of the countable graphs admitting a tree-decompo-sition into primes, is similar to the first and obtained as an easy corollary.

Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family (B_{λ})_{λ<σ} is called a simplicial tree-decomposition of G if the following four 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 ≤ λ < μ < σ).

(S4) Each S_{μ} is contained in B_{λ} for some λ < μ  (μ < σ).  (Fig. 1)

Figure 1

The concept of a simplicial tree-decomposition owes its existence to two sources, simplicial decompositions and tree-decompositions. Both these kinds of decomposition were in turn developed from the decompositions used (for finite graphs) by K. Wagner in his classic paper [ 8 ], in which he proved the equivalence of the 4-Colour-Conjecture to Hadwiger’s Conjecture for n = 5. Wagner’s idea was to break down the graphs under investigation along separating complete subgraphs (‘simplices’), using the fact that, on reassembling, the graphs would essentially inherit the chromatic number of their parts.

Wagner’s decompositions were later redefined—and named ‘simplicial decompositions’—by Halin [ 5 ], to make them suitable also for infinite graphs; the definition given by Halin is essentially equivalent to our conditions (S1)–(S3). It is interesting to note that for finite graphs the conditions (S1)–(S3) imply (S4), which is not the case for infinite graphs. Thus, with the transition to infinite graphs based on (S1)–(S3), one of the most striking features of Wagner’s finite decompositions was lost: their ‘tree-shape’, a consequence of (S4) (see [ 1 ] for details).

It was this ‘tree-shape’ that gave rise to the other generalization of Wagner’s decompositions: the ‘tree-decompositions’ recently introduced by Robertson and Seymour [ 7 ]. Robertson and Seymour’s definition of a tree-decomposition (again for finite graphs) is essentially equivalent to our conditions (S1), (S3) and (S4).

Thus simplicial tree-decompositions, as defined above, are simplicial decompositions as well as tree-decompositions. They are therefore a generalization of Wagner’s decompositions to infinite graphs in the structural sense mentioned, while at the same time maintaining their compatibility with graph properties such as the chromatic number.

Moreover, simplicial tree-decompositions form an interesting object of study in themselves. They have turned out to possess a number of very natural features (see [ 1 ] for an introduction), and some of their most basic properties are still unknown. To give only one example: it is still an open problem to determine which infinite graphs admit a simplicial tree-decomposition (or, equivalently in this case, a simplicial decomposition) into finite factors.

We shall usually call complete graphs simplices (as is the custom in this field), and the S_{μ}’s in (S2) simplices of attachment. The ‘partial union’ ⋃_{λ<μ} B_{λ} appearing in (S2) will be denoted G|_{μ}; it is not difficult to show that every G|_{μ} must be an induced subgraph of G [ 1 ].

A graph is called prime if it has no simplicial tree-decomposition into more than one factor. We remark that the notion of being prime remains the same if it is taken with reference to (S1)–(S3) alone, and that a graph is prime if and only if it contains no separating simplex [ 1 ]. A simplicial tree-decomposition in which all factors are prime will be called a simplicial tree-decomposition into primes, or a prime decomposition.

A subgraph H of G will be called attached to a subgraph H′ of G\H if every vertex of H is adjacent to a vertex in H′.

An example of attached graphs we shall frequently encounter is that of a minimal separator. For disjoint subgraphs X, S, Y of G let us say that S is an X–Y separator in G if V (S) separates X from Y in G in the usual sense, and that S is a minimal X–Y separator if, in addition, X and Y are not separated by any proper subset of V (S). (By a simple application of Zorn’s Lemma, every X–Y separator contains a minimal X–Y separator.) Then for vertices x, y ^{∈} G, an { x }–{ y } (or: x–y) separator S is minimal if and only if S is attached to the component of G\S containing x, as well as to the component containing y.

If S ⊂ G is a simplex and C is a component of G\S to which S is attached, the pair (C, S) will be called a side (of S) in G. For sides (C, S), (C′, S′) in G we write (C, S) ≤ (C′, S′) if C ⊂ C′.

The following lemma, whose straightforward proof can be found in [ 2 ], facilitates the study of ‘nested’ sides.

Lemma 1.1. [ 2 ] (i) The relation ≤ defines a partial order on the set of all sides in G. (ii) (C, S) ≤ (C′, S′) if and only if C ∩ C′ ≠ ∅ and S′ ∩ C = ∅. (iii) (C, S) < (C′, S′) if and only if S ∩ C′ ≠ ∅ and S′ ∩ C = ∅.

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 vertices are 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 spanned 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. We shall usally abbreviate G [ X → Y ] ∩ Y to Y [ X]. Thus, Y [ X] is the subgraph of Y spanned 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.

A graph H ⊂ G will be called convex in G if H contains every induced path in G whose endvertices are in H. Equivalently, H is convex in G iff H is induced in G and, for every x ^{∈} G\H, H [ x] = G [ x → H] ∩ H is a simplex. Moreover, H ⊂ G is convex in G if and only if, for every T ⊂ V (H) and U, W ⊂ V (H)\T, T separates U from W in H iff T separates U from W in G. (Of these three definitions for convexity we shall use whichever one seems most suitable in the given context.) Note that if H is convex in G and H′ ⊂ H, then H′ is convex in H iff H′ is convex in G.

For any induced subgraph X of G, the intersection H of all convex subgraphs of G containing X is again convex; H will be called the convex hull of X in G.

Finally, we shall call H ⊂ G minimally convex in G if H is convex in G and H is not the union of two proper subgraphs that are themselves convex in G (or, equivalently, in H). It is easily shown that if H is minimally convex in G and H′ is a proper convex subgraph of H, then H′ is a simplex [ 1 ]. Since simplices are themselves minimally convex, this means in particular that any convex subgraph of a minimally convex graph is again minimally convex.

Convexity plays an important role in the study of simplicial decompositions and simplicial tree-decompositions. To give just two examples: in any simplicial decomposition (B_{λ})_{λ<σ} of G, the ‘partial unions’ G|_{μ} = ⋃_{λ<μ} B_{λ} (for μ < σ) are convex in G, and in a prime decomposition of G the factors are minimally convex in G (see [ 1 ]).

Recall that, in a prime decomposition, vertices belonging to a common factor are never separated by a simplex. Conversely, we shall call vertices of G (simplicially) close if no simplex separates them, no matter whether G has a prime decomposition or not.

The following lemma, which links simplicial closeness to convexity and prime decompositions, will be a key tool in the proof of our main theorem.

Lemma 1.2. [ 1 ] If the vertices of an induced subgraph X of G are pairwise simplicially close in G, then the convex hull of X in G is prime.

Let G, G′ be graphs, and let f : V (G) → V (G′) be surjective. f is called a homomorphism from G onto G′ if

vw ^{∈} E(G) ⇒ (f(v)f(w) ^{∈} E(G′) ∨ f(v) = f(w))

and

v′w′ ^{∈} E(G′) ⇒ ∃ vw ^{∈} E(G) : (f(v) = v′ ∧ f(w) = w′).

f is called contractive if G [ f^{−1}(v) ] is connected for every v ^{∈} V (G′), and f is simplicial if it is contractive and preserves simplicial closeness. Thus if f is a simplicial homomorphism from G onto G′, then v, w ^{∈} V (G′) can only be separated by a simplex in G′ if every vertex of f^{−1}(v) is separated by a simplex from each vertex of f^{−1}(w) in G.

We shall often identify a vertex of G′ with its inverse image under f, and thus think of V (G′) as being a collection of subsets of V (G), two of which are adjacent if and only if G contains an edge between them.

H′ is said to be a minor of G if G has a subgraph H from which there exists a contractive homomorphism f onto H′. We shall call H′ a simplicial minor of G (and write G ≻_{s} H′), if H and f can be chosen in such a way that H is convex in G and f is simplicial.

Our last lemma will help us handle the factors in prime decompositions. Let us call H maximally prime in G if H is prime and not properly contained in any prime subgraph of G.

Lemma 1.3. [ 1 ] Let H be convex in G. Then the following statements are equivalent:

(i) H is minimally convex;

(ii) H is prime;

(iii) H is maximally prime or an attached simplex.

To illuminate the terms used in this lemma just a little, we remark that all factors in prime decompositions are maximally prime, minimally convex and unattached in the underlying graph; H ⊂ G is unattached in G if H is not attached to any component of G\H [ 1 ].

We conclude this section by quoting the main result of [ 2 ], which will be the starting point for the proof of our main theorem in Section 4.

Recall that, for X, Y ⊂ G, the expression Y [ X] denotes G [ X →Y ]∩Y. For example, if S ⊂ G and C is a component of G\S, then S [ C] is the subgraph of S spanned by all those vertices of S that have a neighbour in C.

If (C, S) is a side in G, S′ ⊂ S, and if X ⊂ G satisfies X ⊃ S′ and X ∩ C ≠ ∅, we shall call X an extension of S′ into C.

Theorem 1.4. [ 2 ] A countable graph G has a simplicial tree-decomposition into primes if and only if G satisfies the following condition: (†) If (C, S) is a side in G and C′ is a component of G\S, C′ ≠ C, then S [ C′] has a

prime extension into C.

2. Two Examples

It is fairly straightforward to show that every finite graph has a prime decomposition into a unique set of factors. For infinite graphs, however, this is surprisingly not the case. The first example of an infinite graph that does not admit a simplicial (tree-) decomposition into primes was already given in Halin’s original paper [ 5 ], and the two graphs we shall study in this section are both variations of this example. In fact, it is the aim of this paper to show that these two graphs are essentially the only countable graphs without prime decompositions: we shall prove that every countable graph admitting no prime decomposition contains at least one of them as a simplicial minor.

Define the graph H_{1} as follows. Let S be a countably infinite simplex, with V (S) = { s_{1}, s_{2}, … } say. Add a one-way infinite path P = x_{1}x_{2} … and a single vertex q, join x_{i} to s_{j} iff i ≥ j, and let q be adjacent to all vertices in S but to none in P.

Let H_{2} be the graph obtained from H_{1} by adding all missing edges between vertices x_{i} and x_{j}, i ≠ j, thus turning P into a simplex (Fig. 2).

Let us consider H_{1}, and try to find a prime decomposition (B_{λ})_{λ<σ} of H_{1}. Recall that all ‘parts’ H_{1}|_{μ} of this decomposition must be convex in H_{1}, and that the factors B_{λ} must be maximally prime and unattached.

Starting ‘from the right’, let us try putting q in the first factor B_{0}. Since B_{0} is prime but q is separated from every vertex of P by the simplex S, we must have B_{0} ∩ P = ∅, i.e. B_{0} ⊂ H_{1} [ S ∪ { q }]. But H_{1} [ S ∪ { q }] is itself a simplex and therefore prime; thus if B_{0} is to be maximally prime in H_{1}, we must have B_{0} = H_{1} [ S ∪ { q }].

Figure 2

Turning now to the second factor, B_{1}, we shall certainly have B_{1} ∩ P ≠ ∅, because B_{1} has to contribute a new vertex of H_{1} to our decomposition (S3). But if x_{i} ^{∈} B_{1} say, then B_{1} cannot contain any of the vertices s_{j} with j > i, because these vertices are separated from x_{i} by the simplex

T_{i} := H_{1} [ s_{1}, s_{2}, …, s_{i}, x_{i+1} ].

(Thus B_{1} has at most finitely many vertices in S; this fact, as well as the simplices T_{i} ‘shielding’ the vertices of P from almost all vertices of S, will have a more general analogue in the proof of our main theorem.)

We therefore have s_{j} ^{∈} S\B_{1} for every such vertex s_{j}, and B_{1} ∩ S separates s_{j} from x_{i} in H_{1}|_{2} = B_{0} ∪ B_{1}. However, no subgraph of S separates any vertex of S from any vertex of P in H_{1}, because S is attached to P. Hence, every possible choice of B_{1} contradicts the requirement that H_{1}|_{2} be convex in H_{1}, and we are unable to complete our prime decomposition of H_{1}.

Let us make a fresh attempt at finding a prime decomposition for H_{1}, this time excluding q from the first factor B_{0}. Since neither S nor its subsimplices are unattached in G, we must have B_{0} ∩ P ≠ ∅.

Let B_{μ} be the factor that contains q; as seen earlier, this will have to be B_{μ} = H_{1} [ S ∪ { q }]. Since B_{0} ∩ P ≠ ∅, we shall therefore have H_{1}|_{μ+1} ∩ P ≠ ∅, as well as S ⊂ H_{1}|_{μ+1}. Thus unless S is already contained in H_{1}|_{μ}, some vertices of P and S will be separated by the subsimplex S ∩ H_{1}|_{μ} of S in H_{1}|_{μ+1}, contrary to the convexity required for H_{1}|_{μ+1}.

But if S ⊂ H_{1}|_{μ}, then S = S_{μ}, so S ⊂ B_{λ} for some λ < μ by (S4). This, however, contradicts our earlier observation that any factor B_{λ} with B_{λ} ∩ P ≠ ∅ has at most finitely many vertices in S.

Therefore H_{1} has no prime decomposition.

The proof that H_{2} has no prime decomposition is similar to that for H_{1}; as the only difference, the simplices T_{i} have to be redefined as

T_{i} := H_{2} [ s_{1}, s_{2}, …, s_{i}, x_{i+1}, x_{i+2}, …].

3. Simplicial Minors

In this section we take a closer look at simplicial minors. Our aim is to examine their suitability for the result we are seeking: a characterization of the countable graphs that admit a simplicial tree-decomposition into primes.

After a little preparation we shall prove two facts in this section: that ≻_{s} is a transitive relation, and that any simplicial minor of a graph admitting a prime decomposition has itself a simplicial tree-decomposition into primes. Notice that the latter fact immediately yields one direction of our main result, Theorem 4.1: since H_{1} and H_{2} have no prime decompositions, neither of these graphs can be the simplicial minor of any graph that has one.

Moreover, the second of these facts is clearly necessary given the first, provided we are to succeed in proving our desired characterization; for if ≻_{s} is transitive, then any graph property defined in terms of forbidden simplicial minors will be closed under taking simplicial minors.

The following notational conventions will be useful for handling homomorphisms. If f is a homomorphism from G onto G′, and if H ⊂ G and H′ ⊂ G′ are induced

subgraphs, we shall abbreviate G′ [ f(V (H)) ] to f(H), and G [ f^{−1}(V (H′)) ] to f^{−1}(H′). Then f|_{f^{−1}(H′)} is a homomorphism from f^{−1}(H′) onto H′ (which is contractive if f is), but f|_{H} is not in general a homomorphism from H onto f(H): since f(H) contains all edges induced by its vertex set in G′, an edge XY of f(H) need not correspond to an edge of H, i.e. one between X ∩ H and Y ∩ H (but see Lemma 3.1 below).

Looking at their definition, we see that all homomorphisms between graphs map simplices to simplices. In the case of contractive homomorphisms, this property extends to the preservation of convexity:

Lemma 3.1. Let G, G′ be graphs, and let f : V (G) → V (G′) be a contractive homomorphism. Then the following assertions hold:

(i) If H ⊂ G is convex in G, then H′ := f(H) is convex in G′, and f|_{H} is a contractive homomorphism from H onto H′.

(ii) If H′ ⊂ G′ is unattached in G′, then H := f^{−1}(H′) is unattached in G.

Proof. (i) Let H and H′ be as stated, and let P be an H′–H′ path in G′ of length at least 2, say with endvertices X, Y ^{∈} V (H′). We prove the convexity of H′ by showing that XY must be an edge of H′. Clearly X ∩ V (H) ≠ ∅ and Y ∩ V (H) ≠ ∅, but all other vertices of P are disjoint from V (H). The interior vertices of P are therefore subsets of V (C) for a common component C of G\H. Since X and Y each induce a connected subgraph in G, meet V (H), and send an edge to an inner vertex of P, this implies that X and Y meet V (H [ C]). By the convexity of H these vertices span a simplex in G, so G contains an X–Y edge. Thus XY ^{∈} E(H′) as desired.

In order to prove that f|_{H} is a contractive homomorphism from H onto H′, we have to show that f^{−1}(X) ∩ H is connected for every X ^{∈} V (H′), and that H contains an X ∩ H – Y ∩ H edge whenever XY is an edge of H′. To show that f^{−1}(X) ∩ H is connected, let x, y ^{∈} f^{−1}(X) ∩ H. Since f^{−1}(X) is connected, x and y are joined by a path P in G with V (P) ⊂ X; we choose P to be induced in G. Then P ⊂ H by the convexity of H, i.e. P ⊂ f^{−1}(X) ∩ H. Similarly, if XY is an edge of H′, then f^{−1}({ X, Y }) contains a path from X ∩ H to Y ∩ H. Chosen induced in G, this path will be contained in H and therefore have an X ∩ H – Y ∩ H edge.

(ii) Suppose H is attached in G, say H = H [ x] for x ^{∈} G\H. By definition of H, we have f(G [ x → H]\H) ∩ H′ = ∅, so f maps every x–H path P ⊂ G to a walk containing an f(x)–H′ path in G′, whose endvertex in H′ is the image of the endvertex of P in H. Hence H = H [ x] implies that H′ = H′ [ f(x) ], so H′ is attached in G′. □

Recall that a contractive homomorphism f from G onto G′ is simplicial if f preserves simplicial closeness, i.e. if f satisfies the implication

v, w ^{∈} V (G) are close in G ⇒ f(v), f(w) are close in G′.

The following lemma lists some basic properties of simplicial homomorphisms. Combined with Lemma 3.1, it reveals a great deal of compatibility between simplicial homomorphisms and simplicial tree-decompositions into primes.

Lemma 3.2. Let G, G′ be graphs, and let f : V (G) → V (G′) be a simplicial homomorphism. Then the following propositions hold:

(i) If H ⊂ G is convex in G, then f|_{H} is a simplicial homomorphism from H onto f(H). (ii) If H ⊂ G is maximally prime in G, then f(H) is maximally prime in G′ or an

attached simplex.

(iii) If H ⊂ G is minimally convex in G, then f(H) is minimally convex in G′. (iv) If H′ ⊂ G′ is convex, then G has a convex subgraph H from which there exists a

simplicial homomorphism g onto H′. H and g can be chosen in such a way that H contains f^{−1}(H′), and that f and g agree on f^{−1}(H′).

Proof. (i) By Lemma 3.1.(i), H′ := f(H) is convex in G, and f|_{H} is a contractive homomorphism from H onto H′. To show that f|_{H} preserves simplicial closeness, let x, y ^{∈} V (H) and suppose that x, y are close in H. Since H is convex in G, x and y are also close in G, so f(x) and f(y) must be close in G′. But then f(x) and f(y) are even close in H′, because H′ is convex in G′.

(ii) If H is maximally prime in G, then H is convex in G, so f(H) is convex in G′ (Lemma 3.1 (i)) and prime (because H is prime; apply (i)). The assertion follows by Lemma 1.3.

(iii) If H is minimally convex in G, then by Lemma 1.3, H is maximally prime in G or a simplex. If H is a simplex, then f(H) is also a simplex and therefore minimally convex in G′. If H is maximally prime on the other hand, f(H) is minimally convex by (ii) and Lemma 1.3.

(iv) Let H be the convex hull of f^{−1}(H′) in G. Then f(H) is convex in G′, so H′ is convex in f(H) (as well as in G′). As is readily verified, f(C) is a component of f(H)\H′ whenever C is a component of H\f^{−1}(H′), and f^{−1}(C′) ∩ H is a component of H\f^{−1}(H′) whenever C′ is a component of f(H)\H′ (use Lemma 3.1.(i)). For each component C of H\f^{−1}(H′) let us select a fixed vertex X(C) from the vertices of S(C) := H′ [ f(C) ] (= f(H) [ f(C)→H′]∩H′); note that S(C) is a non-empty simplex, because f^{−1}(H′) [ C] ≠ ∅ (by definition of H), and H′ is convex in f(H) (Fig. 3).

Let us now define g by setting g|_{f^{−1}(H′)} := f|_{f^{−1}(H′)} and g(x) := X(C_{x}) for x ^{∈} H\f^{−1}(H′), where C_{x} denotes the component of H\f^{−1}(H′) that contains x. It is easily checked that g is a contractive homomorphism: g preserves adjacency, because every S(C) is a simplex, and the inverse image of a vertex X(C) is connected, because S(C) is attached to f(C). Thus all we have to show is that g preserves simplicial closeness. To see this, let x, y ^{∈} V (H) be close in H. Then x, y are close in G because H is convex in G, so X := f(x) and Y := f(y) are close in G′. If x, y ^{∈} f^{−1}(H′), we have g(x) = X, g(y) = Y and X, Y ^{∈} H′, so g(x) and g(y) must be close in H′, because H′ is convex in G′. If x and y are both in H\f^{−1}(H′), then C_{x} = C_{y} (and consequently g(x) = g(y)), because otherwise S(C_{x}) would separate X from Y in f(H) (and hence in G′), contradicting the closeness of X and Y in G′. Finally, if x ^{∈} H\f^{−1}(H′) and y ^{∈} f^{−1}(H′), then by the same argument the closeness of X and Y in G′ implies that Y ^{∈} S(C_{x}), so g(x) = X(C_{x}) and g(y) = Y are adjacent and therefore close. Hence g is a simplicial homomorphism, as claimed. □

Theorem 3.3. If G_{1} ≻_{s} G_{2} and G_{2} ≻_{s} G_{3}, then G_{1} ≻_{s} G_{3}.

Proof. Let H_{1} ⊂ G_{1}, H_{2} ⊂ G_{2} and f : V (H_{2}) → V (G_{3}) be such that H_{i} is convex in G_{i} (i = 1, 2), f is a simplicial homomorphism, and there exists a simplicial homomorphism from H_{1} onto G_{2}. By Lemma 3.2.(iv), we can find a convex subgraph H′_{1} of H_{1} with a simplicial homomorphism g : V (H′_{1}) → V (H_{2}). Then f ∘ g is a simplicial homomorphism from H′_{1} onto G_{3}. Since H′_{1} is also convex in G_{1}, this means that G_{3} is a simplicial minor of G_{1}. □

As a restatement of Theorem 3.3, we find that whenever H is a class of graphs, the graph property

G(H)_{≻_{s}} := { G | H ^{∈} H ⇒ G ⊁_{s} H }

is closed under taking simplicial minors. Thus we can only hope to characterize the class of decomposable graphs in this way if it shares this feature, i.e. if simplicial minors of decomposable graphs are again decomposable.

The following theorem shows that this is indeed so:

Theorem 3.4. If a countable graph G has a simplicial tree-decomposition into primes and H′ is a simplicial minor of G, then H′ has a simplicial tree-decomposition into primes.

Proof. Let (G_{λ})_{λ<σ} be a prime decomposition of G. By a theorem proved in [ 1 ], the factors in any infinite simplicial tree-decomposition can be reordered into a simplicial treedecomposition of order type ω; we may therefore assume that σ ≤ ω. Let H ⊂ G and f : V (H) → V (H′) be such that H is convex in G and f is a simplicial homomorphism. Let us write

H_{λ} := H ∩ G_{λ}  H|_{μ} := H ∩ G|_{μ}  H′_{λ} := f(H_{λ})  H′|_{μ} := f(H|_{μ})

for all λ < σ and μ ≤ σ.

Being the intersection of two convex subgraphs of G, all graphs of the form H_{λ} or H|_{μ} are convex in G (and hence in H). Since f preserves convexity, the graphs of the form H′_{λ} or H′|_{μ} are therefore convex in H′.

Let us show that every H′_{λ} is prime. Notice first that the graphs H_{λ} must be minimally convex (in G and hence in H), because every G_{λ} is minimally convex, and convex subgraphs of minimally convex graphs are again minimally convex. By Lemma 3.2.(iii), the graphs H′_{λ} are therefore minimally convex in H′, and hence prime (by Lemma 1.3).

We remark that our notation for f(H|_{μ}) is compatible with the conventional meaning of H′|_{μ}, i.e. that H′|_{μ} = ⋃_{λ<μ} H′_{λ} for all μ ≤ σ. For clearly

V (f( ⋃_{λ<μ} H_{λ})) = V ( ⋃_{λ<μ} f(H_{λ}))

and

E(f( ⋃_{λ<μ} H_{λ})) = E(H′ [ V (H′|_{μ}) ])

⊃ E( ⋃_{λ<μ} f(H_{λ})) .

To see the reverse inclusion, let XY ^{∈} E(f(⋃_{λ<μ} H_{λ})) be given. Since f induces a simplicial homomorphism from H|_{μ} onto H′|_{μ} (Lemma 3.2.(i)), XY arises from some edge xy ^{∈} E(H) with x ^{∈} X ∩ H|_{μ} and y ^{∈} Y ∩ H|_{μ}. Now if λ(x) denotes the minimal λ with x ^{∈} H_{λ}, λ(y) denotes the minimal λ with y ^{∈} H_{λ}, and λ(x) ≤ λ(y) (say), then xy ^{∈} E(H|_{λ(y)+1}) (because G|_{λ(y)+1} and hence also H|_{λ(y)+1} is an induced subgraph of G), and λ(y) is again minimal with this property. Therefore xy ^{∈} E(H_{λ(y)}), giving XY ^{∈} E(H′_{λ(y)}) and hence XY ^{∈} E(⋃_{λ<μ} f(H_{λ})).

Let Λ denote the set of all ordinals μ < σ for which H′_{μ}\H′|_{μ} ≠ ∅; notice that ⋃_{λ^{∈}Λ|_{μ}} H′_{λ} = H′|_{μ} for all μ ≤ σ, where Λ|_{μ} := Λ ∩ μ (induction on μ). For each μ ^{∈} Λ, put S′_{μ} := f(S_{μ} ∩ H). Since f maps simplices to simplices, every S′_{μ} is a complete subgraph of H′|_{μ}. Two properties of these S′_{μ} are of particular interest to us: the fact that each S′_{μ} coincides with H′_{μ} ∩ H′|_{μ}, and that S′_{μ} separates H′_{μ}\S′_{μ} from H′|_{μ}\S′_{μ} in H′ (for all μ ^{∈} Λ where this is meaningful, i.e. for which H′|_{μ}\S′_{μ} ≠ ∅).

Let us first show that S′_{μ} = H′_{μ} ∩ H′|_{μ}, for all μ ^{∈} Λ. By definition of S′_{μ} we clearly have S′_{μ} ⊂ H′_{μ} ∩ H′|_{μ}, so all we have to check is that f^{−1}(X) has a vertex in S_{μ} for every X ^{∈} V (H′_{μ} ∩ H′|_{μ}), μ ^{∈} Λ. This, however, follows from the fact that S_{μ} ∩ H separates H_{μ}\H|_{μ} from H|_{μ}\H_{μ} in H and f^{−1}(X) is connected.

Let us now show that S′_{μ} separates H′_{μ}\S′_{μ} from H′|_{μ}\S′_{μ} in H′. Since H′_{μ} ∪ H′|_{μ} = H′|_{μ+1} is convex in H′, it suffices to show that S′_{μ} separates these graphs in H′|_{μ+1}, i.e. that H′|_{μ+1} contains no H′_{μ}\S′_{μ} – H′|_{μ}\S′_{μ} edge. This, however, holds because H|_{μ+1} contains no H_{μ}\S_{μ} – H|_{μ}\S_{μ} edge and H|_{μ+1} is convex in H.

(H′_{λ})_{λ^{∈}Λ} is almost a prime decomposition of H′. Indeed, as noted above we have ⋃_{λ^{∈}Λ} H′_{λ} = H′|_{σ} = H′, showing (S1). To verify (S2), recall that the terms H′|_{μ} and S′_{μ} mean what they should in this context, i.e. that H′|_{μ} = ⋃_{λ^{∈}Λ|_{μ}} H′_{λ} and S′_{μ} = H′_{μ} ∩ H′|_{μ}, for all μ ^{∈} Λ. As to (S3), the definition of Λ ensures that H′_{μ}\S′_{μ} ≠ ∅ for all μ. Only the second requirement of (S3), namely that no S′_{μ} must contain any previous H′_{λ}, is not generally satisfied.

We shall resolve this problem following an idea of Halin [ 5 ]. Recall that Λ is finite or of order type ω. Let τ : Λ → Λ be the map defined by setting

τ(λ) := \{ \begin{matrix}λ & if H′_{λ} ⊄ S′_{μ} for all μ ^{∈} Λ \\ min \{ μ ^{∈} Λ | H′_{λ} ⊂ S′_{μ} \} & otherwise; \end{matrix}

note that λ ≤ τ(λ) for all λ ^{∈} Λ, because H′_{λ}\S′_{μ} ⊃ H′_{λ}\H′|_{λ} ≠ ∅ for μ < λ. Put

B_{λ} := H′_{λ} ∪ H′_{τ(λ)} ∪ H′_{τ(τ(λ))} ∪ …

for each λ ^{∈} Λ, and set

Λ′ := { μ ^{∈} Λ | μ = τ(λ) ⇒ λ = μ } .

Let us prove that (B_{λ})_{λ^{∈}Λ′} is a simplicial tree-decomposition of H′ into primes, with simplices of attachment S′_{λ} (λ ^{∈} Λ′). Being the union of a nested sequence of prime graphs, each B_{λ} is certainly prime. Since clearly every H′_{λ} (λ ^{∈} Λ) is contained in B′_{λ} for some λ′ ^{∈} Λ′, λ′ ≤ λ, we further have

H′|_{μ} ⊂ ⋃_{λ^{∈}Λ′|_{μ}} B_{λ} for every μ ≤ σ;

in particular, ⋃_{λ^{∈}Λ′} B_{λ} = H′ (S1).

To establish (S2), we show that, for every μ ^{∈} Λ′, S′_{μ} separates B_{μ}\S′_{μ} from ⋃_{λ^{∈}Λ′|_{μ}} B_{λ}\S′_{μ} in H′ (which in particular implies that B_{μ} ∩ ⋃_{λ^{∈}Λ′|_{μ}} B_{λ} ⊂ S′_{μ}, and therefore B_{μ} ∩ ⋃_{λ^{∈}Λ′|_{μ}} B_{λ} = S′_{μ}). Let x ^{∈} B_{μ}\S′_{μ} and y ^{∈} ⋃_{λ^{∈}Λ′|_{μ}} B_{λ}\S′_{μ} be given (possibly x = y), with y ^{∈} B_{κ} say (κ ^{∈} Λ′|_{μ}). As μ ^{∈} Λ′, μ is not of the form τ^{i}(κ). By definition of τ, this means that not all of the graphs H′_{τ^{j}(κ)} with τ^{j}(κ) < μ can be contained in S′_{μ}; let k ^{∈} { 0, 1, … } be such that H′_{τ^{k}(κ)} ⊄ S′_{μ} and τ^{k}(κ) < μ. Pick y′ ^{∈} H′_{τ^{k}(κ)}\S′_{μ} and x′ ^{∈} H′_{μ}\S′_{μ}. Since B_{μ} and B_{κ} are both prime, S′_{μ} separates neither x from x′ nor y from y′. Yet as shown earlier, S′_{μ} separates x′ from y′ in H′, so S′_{μ} separates x from y, as claimed.

In addition to proving (S2), we have thus shown that B_{λ} ∩B_{μ} ⊂ S′_{μ} whenever λ, μ^{∈} Λ′, λ < μ. Since this implies B_{μ} ⊄ B_{λ} (by B_{μ}\S′_{μ} ⊃ H′_{μ}\S′_{μ} ≠ ∅) and B_{λ} ⊄ B_{μ} (because B_{λ} ⊂ S′_{μ} contradicts μ ^{∈} Λ′ by the definition of τ), we have also established (S3).

Since Λ′ ⊂ σ ⊂ ω, (B_{λ})_{λ^{∈}Λ′} also satisfies (S4); see [ 1 ] for details. □

Let G be the class of countable graphs that have a simplicial tree-decomposition into primes, and let H be the class of all other countable graphs. Then trivially G ⊃ G(H)_{≻_{s}}, and by Theorem 3.4 even G = G(H)_{≻_{s}}. Moreover, this assertion remains valid if we replace H with any set H′ ⊂ H in which every graph of H has a simplicial minor—which leaves us with the challenge to find a minimal such H′.

In the remaining part of this paper we shall prove that this problem has a rather elegant solution: the set H′ = { H_{1}, H_{2} }. Indeed, it is easily seen that neither of H_{1}, H_{2} is a simplicial minor of the other; the task will be to show that at least one of them occurs as a simplicial minor in any graph that has no simplicial tree-decomposition into primes.

4. The Main Result

The following theorem is our main result.

Theorem 4.1. A countable graph G has a simplicial tree-decomposition into primes if and only if neither of H_{1}, H_{2} is a simplicial minor of G.

We have already proved one direction of this theorem: if a countable graph has a simplicial tree-decomposition into primes, then neither H_{1} nor H_{2} can be its simplicial minor—for H_{1} and H_{2} have no prime decomposition, but any simplicial minor of a graph admitting a prime decomposition has one too (Theorem 3.4). In this section we prove the other direction of Theorem 4.1, showing that if a countable graph has no simplicial tree-decomposition into primes, it contains H_{1} or H_{2} as a simplicial minor.

Let G be a countable graph that has no prime decomposition. By Theorem 1.4, there exist a simplex S ⊂ G and distinct components C, C′ of G\S such that S is attached to C and S [ C′] has no prime extension into C. We shall find a simplicial homomorphism f from G [ C ∪ S ∪ C′] onto H_{1} or H_{2}; since G [ C ∪ S ∪ C′] is a convex subgraph of G, the domain of f will be convex in G, as required in the definition of simplicial minors.

Our homomorphism f will map the entire component C′ to the single vertex q of H_{1} (of H_{2}, respectively), the simplex S ⊂ G onto the simplex S in H_{1} (in H_{2}), and most of the component C of G\S to H_{1} [ x_{1}, x_{2}, …] or to H_{2} [ x_{1}, x_{2}, …].

We begin the proof with a generalization of the ‘shields’ T_{i} mentioned in the discussion of H_{1} and H_{2} in Section 2.

Definition. Let T, T′ ⊂ G be simplices satisfying (T \T′) ∩ C ≠ ∅, and let t ^{∈} (T \T′) ∩ C.

(i) T′ is a partial T -shield (at t), if (T′\T) ∩ S [ C′] ≠ ∅ and T′ is a minimal t–s separator for some vertex s ^{∈} S\T′.

(ii) T′ is a T -shield, if T ∩ T′ ∩ C = ∅ and T′ is a partial T -shield at t for every vertex t ^{∈} T ∩ C.

Let us note a few straightforward implications of this definition. Suppose T′ is a partial T -shield at the vertex t ^{∈} (T \T′) ∩ C. Clearly T ⊂ G [ C ∪ S] because t ^{∈} T ∩ C, and T′ ⊂ G [ C ∪ S] because T′ is a minimal t–s separator. Moreover, T′ contains all neighbours of t in S, because these are also neighbours of s; in particular, T′ ⊃ T ∩ S. As S is attached to C, T′ can only separate t from s if it meets C, so T′ ∩ C ≠ ∅. And finally, since T′ cannot separate adjacent vertices, all of T \T′ must be in one component of G\T′, while S\T′ is contained in another component.

Perhaps the most useful property of partial T -shields is that they always exist. Indeed, if T ⊂ G is a simplex and t ^{∈} T ∩ C, then t cannot be simplicially close to every vertex of S [ C′], because in that case the convex hull of S [ C′] ∪ { t } in G would be a prime extension of S [ C′] into C (Lemma 1.2). In particular, we have S [ C′]\T ≠ ∅. Pick a vertex s′ ^{∈} S [ C′]\T, and let P = s′ … t be an induced s′–t path in G with P ∩ S = { s′ }. As t is not close to every vertex of S, there exist a vertex s ^{∈} S and a simplex T′ such that T′ is a minimal t–s separator; let us choose T′ and s in such a way that the unique S–T′ path P′ ⊂ P has minimal length. We shall prove that T′ is a partial T -shield at t by showing that s′ ^{∈} T′, i.e. that P′ has length 0.

Suppose not, and let t′ be the endvertex of P′ in T′. Again, t′ is not simplicially close to every vertex of S; let T′′ be a simplex separating t′ from some s ^{∈} S, and assume without loss of generality that T′′ is a minimal t′–s separator. Then T′′ ∩ P′ ≠ ∅, and therefore (P \P′) ∩ T′′ = ∅; for since t′ /^{∈} T′′, (P \P′) ∩ T′′ ≠ ∅ would mean that P had two non-consecutive vertices in T′′, contrary to our assumption that P is an induced subgraph of G. Hence t′ and t are in the same component of G\T′′, so T′′ is also a minimal t–s separator in G. Since the S–T′′ path P′′ ⊂ P′ is shorter than P′, this contradicts the choice of T′. Therefore s′ ^{∈} T′, so T′ is a partial T -shield at t.

For the definition of f, we shall consider the following two cases.

Case 1. For every simplex T ⊂ G with T ∩ C ≠ ∅ there exists a T -shield.

Case 2. There exists a simplex T ⊂ G with T ∩ C ≠ ∅ such that every partial T -shield T′ satisfies T′ ∩ T ∩ C ≠ ∅.

It should be clear from our earlier observations that these two cases are exhaustive and mutually exclusive.

In principle, the entire proof could from now on be read separately for the two cases: in Case 1, we define f to be a simplicial homomorphism onto H_{1}, whereas in Case 2 the image of f will be H_{2}. However, since the treatment of the two cases is for most of the proof very similar, we shall consider them simultaneously, using the same notation. Thus a single statement may need different kinds of justification, depending on the case for which it is considered.

We begin with a few definitions. For each case separately, we select vertices t_{1}, t_{2}, … ^{∈} C, simplices T_{1}, T_{2}, … ⊂ G [ C ∪ S], and vertices s′_{1}, s′_{2}, … ^{∈} S [ C′]. The vertices t_{i} and s′_{j} will later be mapped to the corresponding vertices x_{i} and s_{j} of H_{1} and H_{2}, and the simplices T_{i} correspond to the minimal separating simplices of H_{1}\{ q } and H_{2}\{ q }.

Case 1. Pick a vertex v ^{∈} C, and put T_{0} := { v }. Let i ^{∈} ℕ, and suppose that t_{j}, T_{j} and s′_{j} have been defined for all j ^{∈} ℕ, j < i, and that T_{i−1} ∩ C ≠ ∅. Pick t_{i} ^{∈} T_{i−1} ∩ C, let T_{i} be a T_{i−1}-shield, and let s′_{i} be any vertex of (T_{i}\T_{i−1}) ∩ S [ C′]. Since S is attached to C and T_{i} separates t_{i} from some s ^{∈} S\T_{i}, we again have T_{i} ∩ C ≠ ∅ (Fig. 4).

Case 2. Let T_{0} denote the simplex T ⊂ G provided in the specification of Case 2. Let i ^{∈} ℕ, and suppose that t_{j}, T_{j} and s′_{j} have been defined for all j ^{∈} ℕ, j < i, and that T_{i−1} ∩ T_{0} ∩ C ≠ ∅. Pick t_{i} ^{∈} T_{i−1} ∩ T_{0} ∩ C, let T_{i} be a partial T_{i−1}-shield at t_{i}, and choose s′_{i} ^{∈} (T_{i}\T_{i−1}) ∩ S [ C′]. To show that again T_{i} ∩ T_{0} ∩ C ≠ ∅, it suffices to check for i > 1 that T_{i} is also a partial T_{0}-shield at t_{i}; this follows, because T_{i−1} separates the vertices of S\T_{i−1} from t_{i−1} and therefore from all vertices of T_{0}\T_{i−1}, so s′_{i} ^{∈} (T_{i}\T_{0}) ∩ S [ C′] ≠ ∅ (Fig. 5).

Since, in both cases, T_{i} is a partial T_{i−1}-shield at t_{i} (for all i ^{∈} ℕ), we have

T_{0} ∩ S ⊂ T_{1} ∩ S ⊂ T_{2} ∩ S ⊂ …  (1)

For all i ^{∈} ℕ, let us set

C_{i}^{−} := G [ t_{i} → T_{i}] \ T_{i}

and

C_{i}^{+} := G [ s′_{i+1} → T_{i}] \ T_{i}

By definition of T_{i}, the graphs C_{i}^{−}, C_{i}^{+} are distinct components of G\T_{i}, the components containing T_{i−1}\T_{i} and S\T_{i}, respectively.

As T_{i} is a minimal t_{i}–s separator for some (and hence every) s ^{∈} S\T_{i}, T_{i} is attached to both C_{i}^{−} and C_{i}^{+}, so (C_{i}^{−}, T_{i}) and (C_{i}^{+}, T_{i}) are sides in G. Let us apply Lemma 1.1.(iii) to show that (C_{i}^{−}, T_{i}) < (C_{i+1}^{−}, T_{i+1}) for all i ^{∈} ℕ. We have to check that T_{i} ∩ C_{i+1}^{−} ≠ ∅, and that T_{i+1} ∩ C_{i}^{−} = ∅. The first of these statements holds, because t_{i+1} ^{∈} T_{i} ∩ C_{i+1}^{−}. As to the latter, we have s′_{i+1} ^{∈} T_{i+1} ∩ C_{i}^{+} and hence T_{i+1} ∩ C_{i}^{+} ≠ ∅. Since T_{i+1} is a simplex and therefore not separated by T_{i}, this implies that T_{i+1} ∩ C_{i}^{−} = ∅. Thus (C_{i}^{−}, T_{i}) < (C_{i+1}^{−}, T_{i+1}), as claimed.

Expressed in terms of components, we therefore have

C_{1}^{−} ⊂ C_{2}^{−} ⊂ C_{3}^{−} ⊂ …  (2)

The components C_{i}^{+} are nested similarly, in the opposite way. Let us check this using Lemma 1.1.(ii). By (1) we have s′_{i+2} ^{∈} S\T_{i+1} ⊂ S\T_{i}, so s′_{i+2} ^{∈} C_{i}^{+} ∩ C_{i+1}^{+}. Thus C_{i}^{+} ∩ C_{i+1}^{+} ≠ ∅. Moreover, t_{i+1} ^{∈} T_{i} ∩ C_{i+1}^{−}, so T_{i} ∩ C_{i+1}^{+} = ∅. Lemma 1.1 (i)–(ii) therefore implies that (C_{i}^{+}, T_{i}) > (C_{i+1}^{+}, T_{i+1}), for all i ^{∈} ℕ. Hence,

C_{1}^{+} ⊃ C_{2}^{+} ⊃ C_{3}^{+} ⊃ …  (3)

Notice finally that in Case 1 we have t_{i+2} ^{∈} C_{i}^{+} for all i ^{∈} ℕ. Indeed, t_{i+2} /^{∈} T_{i} because t_{i+2} ^{∈} T_{i+1} and T_{i+1} ∩ T_{i} ∩ C = ∅ (recall that T_{i+1} is a T_{i}-shield), so t_{i+2} ^{∈} C_{i}^{+}, because t_{i+2} is adjacent to s′_{i+1} and s′_{i+1} ^{∈} C_{i}^{+}. By (3), we thus obtain

t_{j} ^{∈} C_{i}^{+} for all i, j ^{∈} ℕ, i ≤ j − 2 .  (4, Case 1)
Let us put T_{−1} := X_{0} := ∅, and set
X_{i} := G [ t_{i} → T_{i} ∪ X|_{i}] \ (T_{i} ∪ X|_{i}) (i = 1, 2, …)

where X|_{i} := X_{0} ∪ … ∪ X_{i−1},

S_{i} := S ∩ T_{i}\T_{i−1} (i = 2, 3, …),
X := ⋃_{i=1}^{∞} X_{i}  T := ⋃_{i=1}^{∞} T_{i}  S^{−} := ⋃_{i=2}^{∞} S_{i}

and

S_{1} := G [ C ∪ S] ∩ G [ s′_{1} → X ∪ S^{−}] \ (X ∪ S^{−}) .

For convenience, we shall further adopt the notation

G′ := G[⋃_{i=1}^{∞}(X_{i} ∪ S_{i})] .

Notice from the above definitions that

X_{i} ⊂ C_{i}^{−} ⊂ C  for all i ^{∈} ℕ .  (5)

Moreover, as s′_{1} ^{∈} T_{1} and hence s′_{1} ^{∈} T_{i} for every i ^{∈} ℕ (by (1)), s′_{1} is adjacent to every vertex of T other than itself. Therefore any vertex of T is in S_{1} unless it is in some X_{i} or in some S_{j}, j ≥ 2. Hence,

T ⊂ G′ .  (6)

Notice further that for all i, j ^{∈} ℕ, i < j, we have s′_{j} ^{∈} T_{j} as well as s′_{j} ^{∈} S\T_{j−1} ⊂ S\T_{i} ⊂ C_{i}^{+} (cf. (1)). Therefore

T_{j} ∩ C_{i}^{+} ≠ ∅ for i < j ,

and hence

T_{j} ∩ C_{i}^{−} = ∅ for i ≤ j .

By (5), this implies that

T_{j} ∩ X_{i} = ∅  for i ≤ j .  (7)

Thus in particular, (T_{i−1}\T_{i}) ∩ X|_{i} = ∅ for all i ^{∈} ℕ. Therefore

T_{i−1}\T_{i} ⊂ X_{i}  for all i ^{∈} ℕ ,  (8)

by t_{i} ^{∈} T_{i−1}\T_{i} and the definition of X_{i}.

(8) tells us precisely how the vertices of T ∩ C are allocated to the various X_{i}’s or to S_{1}. If a vertex t ^{∈} T ∩ C is contained in only one T_{i} (as always in Case 1), then clearly t ^{∈} X_{i+1} for this i. If t is contained in only finitely many but at least two T_{i}’s (as may happen in Case 2), then (8) implies that t ^{∈} X_{k+1} for k := max { i | t ^{∈} T_{i} }. Finally, if t ^{∈} T_{j} for infinitely many j ^{∈} ℕ, then t is not contained in any X_{i} by (7); since t is adjacent to s′_{1} and t /^{∈} S^{−}, this means that t ^{∈} S_{1}.

We are now ready to define f. For v ^{∈} V (C ∪ S ∪ C′), let us set

f(v) := \{ \begin{matrix}x_{i} & if v ^{∈} X_{i} (i ^{∈} ℕ) \\ s_{i} & if v ^{∈} S_{i} (i ^{∈} ℕ) \\ q & if v ^{∈} C′ . \end{matrix}

In order to prove that this definition indeed establishes f as a well-defined simplicial homomorphism from G [ C ∪ S ∪ C′] onto H_{1} or H_{2}, respectively, we have to check the following facts.

(i) f is defined for all vertices of G [ C ∪ S ∪ C′], i.e. G′ ⊃ G [ C ∪ S]. (ii) f is well-defined, i.e. all the subgraphs X_{i}, S_{i} and C′ are pairwise disjoint. (iii) f is a homomorphism, i.e. G contains an edge between two of the subgraphs X_{i}, S_{i}

and C′ if and only if the images of these two subgraphs are adjacent in H_{1} or H_{2}, respectively.

(iv) f is contractive, i.e. X_{i} and S_{i} are connected for all i ^{∈} ℕ.

(v) f preserves simplicial closeness, i.e. two vertices of G are separated by a simplex whenever their images under f are separated by a simplex.

(i) To prove that G′ ⊃ G [ C ∪S], suppose G [ C ∪S]\G′ ≠ ∅ and let C′′ be a component of G [ C ∪ S]\G′. Then C′′ ⊂ C, because any vertex in C′′ ∩ S would be adjacent to s′_{1}, giving C′′ ⊂ S_{1}. Since C is connected and C′′ ⊂ C, there exists a vertex v ^{∈} G′ ∩ C that has a neighbour w in C′′.

Clearly v /^{∈} S_{i} for i ≥ 2. If v ^{∈} X_{i} for some i ^{∈} ℕ, then v ^{∈} G [ t_{i} → T_{i} ∪ X|_{i}], and v /^{∈} T_{i} ∪X|_{i}. As v, w are adjacent, this implies that also w ^{∈} G [ t_{i} →T_{i} ∪X|_{i}]. But since w /^{∈} G′ and T ⊂ G′ (6), w is in neither of T_{i} or X|_{i}. Therefore w ^{∈} G [ t_{i} → T_{i} ∪ X|_{i}] \ (T_{i} ∪ X|_{i}) = X_{i}, a contradiction. Hence, v /^{∈} X.

By an analogous argument, v cannot be in S_{1}. Thus v /^{∈} X_{i} and v /^{∈} S_{i} for all i ^{∈} ℕ, contrary to our assumption that v ^{∈} G′.

(ii) To see that f is well-defined, observe first that the X_{i}’s are pairwise disjoint by definition, and disjoint from C′ and all S_{j}’s with j ≥ 2 by (5). The S_{i}’s, i ≥ 2, are disjoint from C′ by definition, and they are pairwise disjoint, because S_{j} ∩ T_{j−1} = ∅ and T_{j−1} ⊃ S ∩ T_{i} ⊃ S_{i} for 1 < i < j by (1). Finally, S_{1} is by definition disjoint from C′, from all X_{i}’s, and from S_{j} for all j ≥ 2.

(iii) For a proof that f is a homomorphism, notice first that G contains an S_{i}–S_{j} edge whenever i ≠ j, and an S_{i}–C′ edge for all i (because s′_{i} ^{∈} S_{i} ∩ S [ C′]). Furthermore, G contains no X_{i}–C′ edges for any i (by (5)), and no X_{i}–S_{j} edges if i < j (because X_{i} ⊂ C_{i}^{−} by (5), whereas S_{j} ⊂ S\T_{j−1} ⊂ S\T_{i} ⊂ C_{i}^{+}; cf. (1)). In fact,

T_{i} separates X_{i} from S_{j} in G, for all i, j ^{∈} ℕ, i < j.  (9)

However, G contains an X_{i}–S_{j} edge whenever i > j, namely the edge t_{i}s′_{j} ^{∈} E(T_{i−1}).

Let us now show that G contains an X_{i}–S_{i} edge for every i ^{∈} ℕ. Since s′_{i} ^{∈} T_{i} and T_{i} is a minimal t_{i}–s separator for some s ^{∈} S\T_{i}, there exists a t_{i}–s′_{i} path P ⊂ G with P ∩ T_{i} = { s′_{i} }. We shall assume that P is induced in G. Then P has no non-consecutive vertices in T_{i−1}, so

P ⊂ G [ C_{i−1}^{+} ∪ T_{i−1} ] .

By (7), T_{i−1} ∩ X|_{i} = ∅. Furthermore, X|_{i} ⊂ C_{i−1}^{−} by (2) and (5), so C_{i−1}^{+} ∩ X|_{i} = ∅. Therefore P ∩ X|_{i} = ∅. Combining this with our assumption that P ∩ T_{i} = { s′_{i} }, we obtain P \{ s′_{i} } ⊂ X_{i}. The last edge on P is therefore an X_{i}–S_{i} edge.

It remains to show that G contains the correct edges between different X_{i}’s. In Case 2 we need the existence of an X_{i}–X_{j} edge whenever i ≠ j, which is given in the edge t_{i}t_{j} ^{∈} E(T_{0}). Let us now consider Case 1. We have to show that G contains an X_{i}–X_{i+1} edge for every i ^{∈} ℕ, but no X_{i}–X_{j} edges if i ≤ j − 2. The existence of X_{i}–X_{i+1} edges for all i is shown in exactly the same way as the existence of X_{i}–S_{i} edges was proved above, with t_{i+1} taking over the role of s′_{i}. Turning now to non-consecutive X_{i}’s, we prove a little more than is required at this point, namely that

T_{i} separates X_{i} from X_{j} in G, if i ≤ j − 2.  (10, Case 1)

Since X_{i} ⊂ C_{i}^{−} by (5), it suffices to show that X_{j} ⊂ C_{i}^{+}. Now as T_{i+1} is a T_{i}-shield, we have C ∩ T_{i} ∩ T_{i+1} = ∅, and therefore

T_{i} ∩ C = C ∩ T_{i} \ (C ∩ T_{i} ∩ T_{i+1})
= C ∩ T_{i} \ T_{i+1}
⊂ X_{i+1}
⊂ X|_{j}

by (8) and i + 1 < j. On the other hand,

T_{i}\C = T_{i} ∩ S
⊂ T_{j}

by (1) and i ≤ j. Therefore T_{i} ⊂ X|_{j} ∪ T_{j}, so

X_{j} ∩ T_{i} = ∅

by definition of X_{j}. As t_{j} ^{∈} X_{j} ∩C_{i}^{+} by (4) and X_{j} is connected, this implies that X_{j} ⊂ C_{i}^{+}, completing the proof of (10).

(iv) The fact that all subgraphs X_{i} and S_{i} are connected is immediate from their definitions. Since also C′ is connected, f is contractive.

(v) We finally prove that f preserves simplicial closeness. In H_{2}, all pairs of non-close vertices are of the form { x_{i}, q } or { x_{i}, s_{j} } with i < j. As S ⊂ G separates X_{i} from C′ and T_{i} separates X_{i} from S_{j} in G for all i, j ^{∈} ℕ, i < j (9), these pairs cannot be the images of close vertices of G.

The only additional pairs of non-close vertices existing in H_{1} are of the form { x_{i}, x_{j} } with i ≤ j − 2. They cannot be the images of close vertices of G, because (in Case 1) T_{i} separates X_{i} from X_{j} if i ≤ j − 2 (10).

This completes the proof of Theorem 4.1.

Having proved Theorem 4.1, let us now return to tree-decompositions, i.e. to decompositions satisfying conditions (S1), (S3) and (S4). Clearly a graph is prime with respect to tree-decompositions, that is, it cannot be decomposed into more that one factor, if and only if it is complete. Thus F = (B_{λ})_{λ<σ} is a tree-decomposition of a graph G into primes iff F satisfies (S1), (S3) and (S4) and every B_{λ} is a simplex. But then F also satisfies (S2). Thus F is in fact a simplicial tree-decomposition, and even a simplicial tree-decomposition into primes. Moreover, G has no induced cycles other than triangles, so G is chordal.

Conversely, it is not difficult to show that if G is chordal and F is a simplicial treedecomposition of G into primes, then every B_{λ} is a simplex. Theorem 4.1 therefore implies the following characterization theorem for tree-decompositions.

Theorem 4.2. A countable graph admits a tree-decomposition into primes if and only if it is chordal and neither H_{1} nor H_{2} is its simplicial minor. □

References

1. R. Diestel, Simplicial tree-decompositions of infinite graphs I, submitted.

2. R. Diestel, Simplicial tree-decompositions of infinite graphs II—the existence of prime decompositions, submitted.

3. R. Diestel, Simplicial tree-decompositions of infinite graphs III—the uniqueness of prime decompositions, submitted.

4. G. A. Dirac, Simplicial decompositions of infinite graphs, Symp. Math. Roma XVIII (1986), 159–195.

5. R. Halin, Simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen, Math. Ann. 156 (1964), 216–225.

6. R. Halin, On the representation of triangulated graphs in trees, Europ. J. Combinatorics 5 (1984), 23–28.

7. N. Robertson and P. D. Seymour, Graph minors I–XVIII, J. Combin. Theory B , appearing.

8. K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590.

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