SIMPLICIAL TREE-DECOMPOSITIONS OF INFINITE GRAPHS II The Existence of Prime Decompositions

Reinhard Diestel Department of Pure Mathematics University of Cambridge 16 Mill Lane Cambridge, England

Abstract. In this second of three papers on the same subject we obtain a first characterization of the countable graphs that admit a simplicial tree-decomposition into primes.

This paper is a continuation of [ 4 ]. The problem it tackles, the existence of simplicial tree-decompositions into primes, was introduced in [ 4 ], and all the notation used is explained there. To repeat just the most basic definition, we say that if σ > 0 is an ordinal and F = (B_{λ})_{λ<σ} a family of induced subgraphs of a graph G, then F forms a simplicial tree-decomposition of G, if (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 λ < μ  (μ < σ).

A graph is called prime if it has no such decomposition into more than one factor. A simplicial tree-decomposition in which all factors are prime is a simplicial tree-decomposi-tion into primes, or a prime decomposition.

The bulk of this paper is devoted to proving one theorem: a characterization of the countable graphs that admit a simplicial tree-decomposition into primes (Theorem 1). The slightly more general problem to characterize the graphs admitting any simplicial decomposition into primes was posed by Halin in 1964 [ 8 ]. It has since stood unresolved, although a sufficient condition [ 8 ] and some necessary conditions (Dirac [ 7 ]) have been known. Our solution is independent of [ 8 ] and [ 7 ].

Section 1 contains the proof of Theorem 1. In Section 2 we give two examples illustrating the theorem. In Section 3 we briefly present a result based on Theorem 1, which will be proved in a forthcoming paper [ 6 ]. This result characterizes the decomposable graphs in a Kuratowski-like fashion, by two forbidden ‘simplicial’ minors.

1. The Existence of Prime Decompositions: A Characterization Theorem

The following theorem is the main result of this paper.

Theorem 1. 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.

Before we think about proving Theorem 1, let us illustrate condition (†) by noting two properties it implies.

Lemma 2. Let G be a graph that satisfies (†). Then G has the following two properties: (i) If (C, S) is an inaccessible side of S in G, then (C, S) is the only side of S in G. (ii) A simplex S ⊂ G has an inaccessible side if and only if S is maximally prime and

attached in G.

Proof. (i) Let (C, S) be an inaccessible side in G, and C′ a component of G\S, C′ ≠ C. If (C′, S) is also a side in G, i.e. if S is attached to C′, then (†) implies that S has a prime extension into C. This contradicts the assumption that (C, S) is inaccessible.

(ii) If S is maximally prime and attached in G, say to C, then (C, S) is clearly an inaccessible side. Conversely, if (C, S) is inaccessible and \overline{S} ⊃ S is maximally prime in G, then clearly \overline{S} ∩ C = ∅. But \overline{S} cannot have a vertex in any other component of G\S either, because then S would be attached to this component, contradicting (i). Hence \overline{S} = S, i.e. S is maximally prime in G. □

The proof that (†) is necessarily satisfied by any graph that has a prime decomposition (countable or not), is an easy application of [ 4, Theorem 3.2 ]. Let G be a graph, suppose that (B_{λ})_{λ<σ} is a prime decomposition of G, and let C, S and C′ be given as in (†). Let \overline{S} ⊃ S be a maximal simplex in G. Suppose first that \overline{S} = S, i.e. that S is itself a maximal simplex. Then [ 4, Theorem 3.2 ] applies directly to S. If Λ(S) is finite, then S has a prime extension into C by (ii). If Λ(S) is infinite, then λ(C) < sup^{+}Λ(S) by (iii). Moreover, S is not attached to C′ (also by (iii)), so S [ C′] ⫋ S and Λ(S [ C′]) is finite. Choose μ ^{∈} Λ(S) in such a way that μ > λ(C) and μ > max Λ(S [ C′]). Then B_{μ} ⊃ S|_{μ} ⊃ S [ C′] and B_{μ} ∩ C ≠ ∅ [ 4, Lemma 1.6 (i)–(ii) ], so B_{μ} is a prime extension of S [ C′] into C.

Suppose now that \overline{S} ≠ S, i.e. that \overline{S}\S ≠ ∅. Let \overline{C} denote the component of G\S that contains \overline{S}\S. If \overline{C} = C, we are done. But if \overline{C} ≠ C, then C is also a component of G\\overline{S}, and \overline{S} [ C] = S ⫋ \overline{S}. Therefore [ 4, Theorem 3.2 ], applied to \overline{S}, ensures the existence of a prime extension of S into C.

This completes the necessity part of the proof.

We now show that a countable graph G has a prime decomposition if it satisfies (†). The proof will be organized as follows. We shall consider a maximal family F =

(B_{λ})_{λ<σ} of subgraphs of G, subject to a number of conditions. This family will trivially form a prime decomposition of its union G′, and we shall have to show that it covers the entire graph G.

The conditions imposed on the families considered will serve two purposes. Firstly, they will ensure that each B_{λ} conforms to the basic requirements for factors in a prime decomposition, e.g. that each B_{λ} is maximally prime in G and unattached (cf. [ 4, Theorem 1.10 ]). Secondly, the conditions will have to ensure that at each ‘stage’ G|_{μ} in the construction of F such new subgraphs are indeed available and can be considered for selection as B_{μ}; this will restrict the choice of factors at earlier stages. From a more global point of view, we can say that the conditions have to organize the order in which certain factors are selected, so as to avoid ‘traps’ of the kind illustrated in [ 4, Section 4 ]. The organization of this order will depend on the structure of G as well as on a fixed enumeration of its vertices.

Before we can get down to the main part of the proof (as loosely described above), we have to make some preparations.

We begin by developing a tool for assessing the positions of potential factors within G: we define a partial order on the set of all sides in G, i.e. of all pairs (C, S) where S ⊂ G is a simplex, C a component of G\S, and S is attached to C.

We shall then use this concept to show that a prime extension of S [ C′] into C as in (†) can in fact always be chosen maximally prime and unattached (Lemmas 4,6,7)— which gives us a stronger version of (†) needed to find (unattached) new factors in our construction of a decomposition of G.

If G is a graph, let H := H(G) denote the set of all sides in G, i.e. the set of all pairs (C, S) where S is a simplex in G, C a component of G\S, and S is attached to C. For (C, S), (C′, S′) ^{∈} H write (C, S) ≤ (C′, S′) iff C ⊂ C′.

Lemma 3. (i) ≤ defines a partial order on H;

(ii) (C, S) ≤ (C′, S′) if and only if C ∩ C′ ≠ ∅ and S′ ∩ C = ∅, for all

(C, S), (C′, S′) ^{∈} H; (iii) (C, S) < (C′, S′) if and only if S ∩ C′ ≠ ∅ and S′ ∩ C = ∅, for all

(C, S), (C′, S′) ^{∈} H.

Proof. (i) ≤ is clearly reflexive and transitive. To see the antisymmetry of ≤ , suppose that (C, S), (C′, S′)^{∈} H satisfy C ⊂ C′ and C′ ⊂ C. We have to show that S = S′. Suppose this is false, say S\S′ ≠ ∅. Since S\S′ is attached to C and C = C′, the component of G\S′ containing S\S′ can only be C′. Thus S ∩ C = S ∩ C′ ≠ ∅, a contradiction.

(ii) If (C, S) ≤ (C′, S′), then clearly C ∩ C′ = C ≠ ∅ and S′ ∩ C ⊂ S′ ∩ C′ = ∅. Conversely, if C has a vertex in C′ but does not meet S′, then C ⊂ C′.

(iii) If (C, S) < (C′, S′), then S′ ∩ C = ∅ and C ∩ C′ ≠ ∅ as in (ii). S ∩ C′ ≠ ∅ holds, because otherwise (C, S) ≥ (C′, S′) by (ii). Conversely, if S has a vertex s in C′ and C ∩ S′ = ∅, then every neighbour of s in C is also in C′, giving C ∩ C′ ≠ ∅ because S is attached to C. By (ii) and S′ ∩ C = ∅ this implies (C, S) ≤ (C′, S′), and therefore (C, S) < (C′, S′). □

As an immediate consequence of Lemma 3 let us note that (C, S) ≤ (C′, S′) implies G [ C → S] ⊂ G [ C′ → S′].

Let H′ ⊂ H, and let C be a strictly descending chain of elements (C, S) of H′. We shall call C maximal with respect to extension in H′, if C is not bounded below by any element of H′\C. By Zorn’s Lemma, every non-empty subset H′ of H contains at least one such maximal chain.

The following three lemmas provide us with strengthenings of condition (†). We first show that the component C′ in the condition can be replaced with any finite number of components of G \ (S ∪ C):

Lemma 4. Let (C, S) be a side in a graph G, let S_{1}, S_{2} ⊂ S, and suppose that S_{1} and S_{2} have prime extensions into C. Then S_{1} ∪ S_{2} has a prime extension into C.

Proof. Let B_{1} be a prime extension of S_{1} into C, and let H be the simplicial neighbourhood of S_{2} in G. Since by assumption S_{2} has a prime extension into C, we have H ∩ C ≠ ∅.

If H ∩ B_{1} ∩ C ≠ ∅, let x ^{∈} H ∩ B_{1} ∩ C; then x is simplicially close in G to every vertex of S_{1} ∪ S_{2}. If H ∩ B_{1} ∩ C = ∅ on the other hand, let x ^{∈} C [ B_{1} ∩ C → H ∩ C] ∩ H. Then x is again close to every vertex of S_{2}; let us show that x is also close to every vertex of S_{1}. Suppose not, and let T ⊂ G be a simplex separating x from some s ^{∈} S_{1}. Since the vertices of S_{2} are close to x as well as to s (by G [ S_{2} ∪ { s }] ⊂ S), T must contain S_{2}. Then, by the definition of H, T ⊂ H. But by the choice of x and the fact that S_{1} is attached to B_{1} ∩ C (because B_{1} is prime), no subgraph of H can separate x from s in G, a contradiction. Thus again x is close to every vertex of S_{1} ∪ S_{2}.

Therefore the vertices of S_{1} ∪ S_{2} ∪ { x } are pairwise close in G, so the convex hull of S_{1} ∪ S_{2} ∪ { x } in G is prime and meets C (cf. [ 4, Proposition 1.4 ]). □

As a brief diversion, let us note an immediate consequence of Lemma 4, which seems potentially useful for tackling the unsolved problem of determining which graphs admit a simplicial (tree-)decomposition into finite factors:

Corollary 5. If (C, S) is a side in a graph G, then every finite S′ ⊂ S has a prime extension into C.

Proof. Let V (S′) := { s_{1}, …, s_{n} }. As S is attached to C, each s_{i} has a neighbour x_{i} in C, and hence the trivial prime extension G [ { s_{i}, x_{i} }] into C. The assertion follows by induction on n. □

The next lemma essentially says that the prime extensions provided by (†) are without loss of generality maximally prime and unattached, which we need in order to use (†) for finding new factors in the construction of a prime decomposition.

Lemma 6. Let G be a countable graph that satisfies (†), let (C_{0}, S_{0}) be an inaccessible side in G, and suppose that S′_{0} ⊂ S_{0} has a prime extension into C_{0}. Then S′_{0} has an extension B into C_{0} that is maximally prime and unattached in G.

Proof. Let G, C_{0}, S_{0} and S′_{0} be given as stated, and let V (G) = { v_{1}, v_{2}, … } be a fixed enumeration of the vertices of G. Note that S_{0} is maximally prime in G (by Lemma 2). Suppose the assertion fails. Then every maximal prime extension B of S′_{0} into C_{0} is attached in G, and therefore a simplex having exactly one (inaccessible) side (recall that B must be maximally prime in G, and use [ 4, Corollary 1.5 ] and Lemma 2). We shall construct a sequence of such extensions of S′_{0} with ‘nested’ sides, whose ‘intersection’ will be the desired graph B.

Figure 1

To be more precise, we shall find a sequence (S_{n})_{n=0,1,...} of extensions of S′_{0} satisfying (a) S_{n} is maximally prime in G

(b) S_{n} ⊃ S′_{n−1}

(c) (C_{n}, S_{n}) < (C_{n−1}, S_{n−1})

(d) k(n) > k(n − 1) (n = 1, 2, …), where

S′_{n} := G [ S_{n−1} → S_{n}] ∩ S_{n}  (n = 1, 2, …),
k(n) := min { k | v_{k} ^{∈} C_{n} }  (n = 0, 1, …),

and C_{n} is the component of G\S_{n} to which S_{n} is attached (Fig. 1).

Before we think about constructing such a sequence (S_{n})_{n=0,1,...}, let us see how it will help us to find our desired unattached prime extension B of S′_{0}.

Notice first that S′_{n−1} ⊂ S′_{n} ⊂ S_{n} for every n ^{∈} ℕ, by (b) and the definition of S′_{n}. Hence,

S′_{0} ⊂ S′_{1} ⊂ ….

By (c), we further have

G [ C_{0} → S_{0} ] ⊃ G [ C_{1} → S_{1} ] ⊃ ….

Now let

B := ⋂_{n=0}^{∞} G [ C_{n} → S_{n}].

Since S′_{n} ⊂ S′_{m} ⊂ S_{m} ⊂ G [ C_{m} → S_{m}] for every m ≥ n, and the graphs G [ C_{m} → S_{m}] form a descending sequence, B contains every S′_{n}. But also conversely, every vertex of B must be in some S′_{n}. To see this, let any vertex v = v_{k} of B be given. Since (k(n))_{n=0,1,...} is strictly increasing, v cannot be contained in every C_{n} and must therefore be in some S_{n}. Then by (C_{n+1}, S_{n+1}) < (C_{n}, S_{n}), v cannot be in C_{n+1} either, so again v ^{∈} S_{n+1}, i.e. v ^{∈} S_{n+1} ∩ S_{n} ⊂ S′_{n+1}. Therefore

B = ⋃_{n=0}^{∞} S′_{n}.

Note, however, that B is not contained in any one S′_{n}. For since S_{n} is attached to C_{n} and S_{n+1} ∩ C_{n} ≠ ∅ (by (c) and Lemma 3), S_{n+1} ∩ S_{n} does not separate S_{n+1}\S_{n} from S_{n}\S_{n+1}; thus S′_{n+1} ∩ C_{n} ≠ ∅, giving S′_{n+1}\S′_{n} ≠ ∅.

Since B is a simplex, all we have to show now is that B is unattached in G—for unattached simplices are necessarily maximally prime [ 4, Corollary 1.9 ]. We show this by proving that for every x ^{∈} G\B there exists a vertex y ^{∈} B such that every x–y path in G has an interior vertex in B. Let x ^{∈} G\B be given. By definition of B, we have x ^{∈} G \ G [ C_{n} → S_{n}] for some n. Let y be a vertex of B satisfying y ^{∈} S′_{n+2}\S′_{n+1}; clearly y ^{∈} C_{n}, since otherwise y ^{∈} S_{n} ∩ S_{n+1} ⊂ S′_{n+1} (by (c) and definition of S′_{n+1}). Let P be any x–y path in G. Since S_{n} separates x and y in G, P contains a subpath from S_{n} to y, and therefore passes through S′_{n+1} ⊂ B (by the choice of y). Hence B is unattached in G, as claimed.

Let us now construct a sequence (S_{n})_{n=0,1,...} that satisfies (a)–(d). Suppose we have found S_{0}, …, S_{n} (n ≥ 0) conforming to (a)–(d). Let H′ denote the set of all inaccessible sides in H(G), i.e. of all sides (C, S) in G for which S is maximally prime. Let

H_{n+1} := { (C, S) ^{∈} H′ | (C, S) ≤ (C_{n}, S_{n}), v_{k(n)} ^{∈} C, S′_{n} ⊂ S }.

Since (C_{n}, S_{n}) ^{∈} H_{n+1}, H_{n+1} is not empty.

Suppose first that H_{n+1} has a minimal element (C, S). By (†) and the definition of S′_{n}, S′_{n} has a maximal prime extension S′ into C (consider C′ := G [ S_{n−1} → S]\S in (†) if n ≥ 1; if n = 0 and S ≠ S_{0}, put C′ := G [ S_{0} → S]\S; if (C, S) = (C_{0}, S_{0}), the existence of S′ is assumed in the assertion of the Lemma). Let H be the convex hull of S ∪ S′ in G. Since S and S′ are both maximally prime, H has a separating simplex T. By the minimality of H as a convex supergraph of S and S′, every component of H\T contains a vertex of S ∪ S′. Thus H\T has exactly two components: one containing S\T, the other containing S′\T (and neither S\T nor S′\T is empty). Since S is attached to C, T cannot be contained in S, so T ∩ C ≠ ∅. (However, T may well be a subgraph of S′.) By the convexity of H, T also separates S\T and S′\T in G; let T′ ⊂ T be a minimal S\T –S′\T separator in G. Then T′ is attached to G [ S → T′]\T′ as well as to G [ S′ → T′]\T′ (Fig. 2).

By (†), we can choose S_{n+1} to be a maximal prime extension of T′ into G [ S′ → T′]\T′ (ensuring (a) for n + 1). Then S_{n+1} ⊃ T′ ⊃ S′∩S ⊃ S′_{n} ⊃ S′_{0} (ensuring (b)), so by assumption S_{n+1} is attached in G, say to C_{n+1}. Since S_{n+1} [ S] = T′ ⫋ S_{n+1}, we have S ∩ C_{n+1} = ∅. On the other hand, S_{n+1} ∩ C ⊃ T′ ∩ C ≠ ∅ by definition of S′ and T′.Lemma 3 therefore gives (C_{n+1}, S_{n+1}) < (C, S) ≤ (C_{n}, S_{n}), as required in (c). Finally, v_{k(n)} cannot be in C_{n+1}, because otherwise we would have (C_{n+1}, S_{n+1}) ^{∈} H_{n+1}, contrary to the minimality of (C, S) in H_{n+1}. Therefore k(n + 1) > k(n) (using C_{n+1} ⊂ C_{n}), establishing (d).

Hence S_{n+1} satisfies (a)–(d), as required.

Suppose now that H_{n+1} has no minimal element. Let C be a descending chain in H_{n+1} that is maximal with respect to extension, and define

H^{−} := ⋂_{(C,S)^{∈}C} G [ C → S] ,  D^{−} := ⋂_{(C,S)^{∈}C} C ,  S^{−} := H^{−}\D^{−}.

Notice that S′_{n} ⊂ S^{−} (because S′_{n} ⊂ S for every (C, S) ^{∈} C), and that v_{k(n)} ^{∈} D^{−}. Note further that the definition of S^{−} is such that every s ^{∈} S^{−} is contained in S for some (C, S) ^{∈} C. Moreover, if s ^{∈} S then s cannot be in C′ for any (C′, S′) ^{∈} C, (C′, S′) < (C, S), so s will be in S′ for every (C′, S′) subsequent to (C, S) in C. Thus any two elements s, s′ of S^{−} are contained in some common S, (C, S) ^{∈} C, and are therefore adjacent. Hence, S^{−} is a simplex. To mention one last property of S^{−}, we remark that S^{−} separates every x ^{∈} D^{−} from every y ^{∈} G\H^{−}. This is easily checked by considering the first vertex in ⋃_{(C,S)^{∈}C} S on any (fixed) x–y path in G.

Let C^{∗} be the component of D^{−} containing v_{k(n)}, and put S^{∗} := S^{−} [ C^{∗}]. Notice that S^{∗} ∩ C ≠ ∅ for every (C, S) ^{∈} C: for if S^{∗} ⊂ S and (C′, S′) ^{∈} C, (C′, S′) < (C, S), then S′ ∩ S (⊃ S^{∗}) separates S′\S from v_{k(n)}, contradicting v_{k(n)} ^{∈} C′.

Let S_{n+1} ⊃ S^{−} be maximally prime in G (possibly S_{n+1} = S^{−}). Since S_{n+1} ⊃ S^{−} ⊃ S′_{n} ⊃ S′_{0} , S_{n+1} is by assumption attached in G—say to C_{n+1}—and satisfies (a)–(b).

In order to verify (c), i.e. to check that (C_{n+1}, S_{n+1}) < (C_{n}, S_{n}), we have to show that C_{n+1} ⊂ D^{−}. Suppose the contrary, i.e. that C_{n+1}\H^{−} ≠ ∅. Since S^{−} separates D^{−} from G\H^{−} but does not separate C_{n+1}, this means that in fact C_{n+1} ⊂ G\H^{−} (and S_{n+1}\S^{−} ⊂ G\H^{−}); in particular, C^{∗} ∩ C_{n+1} = ∅. By (†), we can therefore find a prime extension B^{∗} of S^{∗} into C_{n+1}; let x ^{∈} B^{∗} ∩ C_{n+1}. Since x ^{∈} G\H^{−}, we have x ^{∈} G\G [ C → S] for some (C, S) ^{∈} C. Then S separates x from B^{∗} ∩ C, which is nonempty, because B^{∗} ⊃ S^{∗} and S^{∗} ∩ C ≠ ∅. This contradicts the fact that B^{∗} is prime, completing the proof of (c).

It remains to show (d), i.e. that v_{k(n)} /^{∈} C_{n+1}. This, however, follows immediately from the maximality of C and the fact that C_{n+1} ⊂ D^{−} (giving (C_{n+1}, S_{n+1}) < (C, S) for each (C, S) ^{∈} C). □

The reader will have noticed that Lemma 6 gives in fact more than a straightforward strengthening of (†): it provides an unattached maximal prime extension into C of any subsimplex S′ of S that has some prime extension into C (for an inaccessible side (C, S) of G), regardless of whether S′ has the form S [ C′] for some other component C′ of G\S.

We can therefore combine Lemmas 4 and 6 to a rather powerful tool for extending partial decompositions of a graph:

Lemma 7. Let G be a countable graph that satisfies (†), let (C, S) be a side in G, and let C_{1}, …, C_{n} be components of G\(C ∪ S), n ^{∈} ℕ. Then

S′ := ⋃_{i=1}^{n} S [ C_{i}]

has an extension into C that is maximally prime and unattached in G.

Proof. Suppose first that (C, S) is inaccessible. Using (†), Lemma 4 and induction on n, we see that S′ has some prime extension B into C. By Lemma 6 we may assume that B is unattached and maximally prime in G.

Suppose now that (C, S) is accessible, and let B be a maximal prime extension of S into C. Then B is maximally prime in G. If B is unattached, we are done; suppose therefore that B is attached to a component D of G\B. Then B is a simplex [ 4, Corollary 1.5 ], and (D, B) is an inaccessible side in G. Moreover, we have (D, B) < (C, S), because S ∩ D = ∅ and B ∩ C ≠ ∅ (Lemma 3). Therefore D ⊂ C, and hence D ∩ C_{i} = ∅, i = 1, …, n. Again by Lemma 4 (and induction), we can therefore find a prime extension of S′ into D, which by Lemma 6 can be chosen to be maximally prime and unattached in G. □

Our last lemma looks somewhat technical, but it expresses a rather simple and useful fact. It basically gives us some leeway slightly to alter a specified part of a convex subgraph, while preserving its convexity. We shall need this lemma when, in the process of constructing a prime decomposition of a graph G, the most recent factor B_{μ}^{1} has to be replaced by an alternative unused maximally prime subgraph B_{μ}^{2}, while preserving the convexity of G|_{μ+1} already established for G|_{μ} ∪ B_{μ}^{1}.

Lemma 8. Let G be a graph, and let H, B_{1}, B_{2} ⊂ G be such that H is convex and B_{2} is maximally prime in G. Let S_{i} := B_{i} ∩ H and H_{i} := B_{i} ∪ H, i = 1, 2, and suppose that

(i) B_{1}, B_{2} ⊄ H, (ii) S_{1} ⊂ S_{2}, (iii) H_{1} is convex in G, (iv) S_{1} does not separate B_{1}\H from B_{2}\H in G. Then H_{2} is convex in G, and S_{2} = S_{1}.

Proof. Let B′_{2} be a component of B_{2}\H, and let S := H [ B′_{2} ]. As H is convex, S is a simplex, and since B_{2} is prime, this means that S_{2} ⊂ S (and B′_{2} = B_{2}\H). Hence S_{1} and S_{2} are both simplices.

If H ⊂ B_{1}, then H = S_{1} = S_{2} and H_{2} coincides with B_{2}, which is convex by [ 4, Corollary 1.5 ]. Let us therefore assume that H ⊄ B_{1}, i.e. that H\S_{1} ≠ ∅.

Since H_{1} is convex, S_{1} separates B_{1}\S_{1} from H\S_{1} in G. As B_{2} is prime and therefore not separated by S_{1}, this implies by (iv) that S_{1} separates B_{2}\S_{1} from H\S_{1}. In particular (B_{2} ∩ H)\S_{1} = ∅, so by (ii) S_{1} = S_{2}. Furthermore, if P is any H_{2} – H_{2} path in G, the endvertices x, y of P are either both in H or both in B_{2}. As H and B_{2} are each convex, xy must be an edge of G, so H_{2} is convex as claimed. □

We are now ready to begin on the central part of our proof. Let G be a countable graph, V (G) = { v_{1}, v_{2}, … } its vertex set, and suppose that G satisfies (†). As earlier, let H denote the set of all sides in G.

In view of the discussion in [ 4, Section 4 ] of the graphs H^{1} and H^{2}, and the traps they contained for the construction of a prime decomposition, let us say that a subgraph B of G defuses a side (C, S) ^{∈} H if either B ∩ C ≠ ∅ or B ⊃ S. Whenever F = (B_{λ})_{λ<σ} is a family of induced subgraphs of G and μ ≤ σ, call (C, S) ^{∈} H defused at G|_{μ} := ⋃_{λ<μ} B_{λ} if some B_{λ} with λ < μ defuses (C, S), and undefused (at G|_{μ}) otherwise.

Let F be the set of all well-ordered families F of induced subgraphs of G (F = (B_{λ})_{λ<σ} say) satisfying the following seven conditions:

(i) every B_{λ} is maximally prime in G (λ < σ), (ii) every B_{λ} is unattached in G (λ < σ), (iii) B_{μ}\G|_{μ} ≠ ∅ (where G|_{μ} := ⋃_{λ<μ} B_{λ}) (μ < σ), (iv) each S_{μ} (:= B_{μ} ∩ G|_{μ}) is contained in some B_{λ}, λ < μ (0 < μ < σ),

(v) each G|_{μ} is convex in G (μ ≤ σ), (vi) if H_{μ}^{1} ≠ ∅ then B_{μ} ⊂ H_{μ} (μ < σ), (vii) if H_{μ}^{1} = ∅ and H_{μ}^{2} ≠ ∅ then B_{μ} ⊃ S for some (C, S) ^{∈} H_{μ}^{2} (μ < σ),

where H_{μ}^{1}, H_{μ}^{2} and H_{μ} are defined as follows.

An induced subgraph B of G is called eligible at G|_{μ} (μ ≤ σ) if selecting it as B_{μ} is compatible with (i)–(v), i.e. if B is maximally prime and unattached, B\G|_{μ} ≠ ∅, B ∩ G|_{μ} ⊂ B_{λ} for some λ < μ, and B ∪ G|_{μ} is convex in G. (C, S) ^{∈} H is called defusable at G|_{μ} (μ ≤ σ) if (C, S) is undefused at G|_{μ} and G has a subgraph B that is eligible at G|_{μ} and defuses (C, S). If this B can be chosen such that B ∩ C ≠ ∅ (or, equivalently, B ⊂ G [ C → S]), we call (C, S) 1-defusable; otherwise (C, S) is 2-defusable (at G|_{μ}). Then H_{μ}^{1}, H_{μ}^{2} and H_{μ} are defined by setting

H_{μ} := { (C, S) ^{∈} H | (C, S) is defusable at G|_{μ} }

k(μ) := \{ \begin{matrix}∞ & if H_{μ} = ∅ \\ min \{i | ∃ (C, S) ^{∈} H_{μ} : v_{i} ^{∈} C\} & if H_{μ} ≠ ∅ \end{matrix}

H_{μ}^{1} := {(C, S) ^{∈} H_{μ} | (C, S) is 1-defusable at G|_{μ} and v_{k(μ)} ^{∈} C}
H_{μ}^{2} := {(C, S) ^{∈} H_{μ} | (C, S) is 2-defusable at G|_{μ} and v_{k(μ)} ^{∈} C}
H_{μ} := ⋂_{(C,S)^{∈}H_{μ}^{1}} G [ C → S]  (μ ≤ σ).

Thus if we view F as being created by selecting its members B_{λ} inductively, conditions (i)–(v) ensure that F is a prime decomposition of ⋃_{λ<σ} B_{λ}, while conditions (vi) and (vii) express certain preferences in choosing the factors. Broadly speaking, we can think of each B_{μ} as being selected by the following procedure.

Having arrived at G|_{μ}, we first determine whether B_{μ} can be chosen such as to defuse any undefused side at all. If not, we let B_{μ} be any induced subgraph of G that is eligible at G|_{μ} (note that this is the case when H_{μ} is empty, so (vi) and (vii) do not apply). On the other hand, if there are sides defusable at G|_{μ}, we try to select B_{μ} in such a way that it defuses a side (C, S) among these for which C contains a vertex of smallest possible index k. Additional preference is given to those factors B that defuse some such side (C, S) by satisfying B ∩ C ≠ ∅; moreover, if such B exist at all, we even insist that B satisfy B ∩ C ≠ ∅ for every 1-defusable (C, S) with v_{k} ^{∈} C, i.e., that B ⊂ H_{μ}. If, on the other hand, the only way an eligible B can defuse some such side (C, S) is by satisfying B ⊃ S, we take B_{μ} to be any of these B.

For two families F, F′ ^{∈} F, say F = (B_{λ})_{λ<σ} and F′ = (B′_{λ})_{λ<σ′}, let us write F ≤ F′ if σ ≤ σ′ and B_{λ} = B′_{λ} for all λ < σ. Then ≤ defines a partial order on F. By Zorn’s Lemma F has a maximal element, for since the union of a nested sequence of convex subgraphs of G is again convex in G (cf. (v)), every chain in F is bounded by the union of its members.

Let F^{∗} = (B_{λ})_{λ<σ} be a fixed maximal element of F. We shall prove that F^{∗} is a prime decomposition of G.

It is easily seen that F^{∗} is a prime decomposition of G′ := ⋃_{λ<σ} B_{λ} (= G|_{σ}). Indeed, by assumption each B_{λ} is prime, and F^{∗} satisfies (S1) and (S4). Thus all we have to check is that every S_{μ} is a simplex, and that no S_{μ} contains any B_{λ}, λ < μ. (The other requirement of (S3) is met because of (iii).) To see this, let μ < σ, and consider a component C of B_{μ}\G|_{μ}. As G|_{μ} is convex in G, S := G|_{μ} [ C] is a simplex. But B_{μ}, being prime, is not separated by any simplex, so B_{μ}\G|_{μ} is in fact equal to C, and S_{μ} ⊂ S. Moreover, S_{μ} is attached to B_{μ}\G|_{μ}, so S_{μ} cannot contain any B_{λ}, λ < μ (by (ii)).

It remains to show that F^{∗} is a decomposition of the entire graph G, i.e. that G′ = G. Suppose G\G′ ≠ ∅. If H_{σ} = ∅, let v be any vertex of G\G′; otherwise set v := v_{k(σ)}. Let C_{σ} := G [ v → G′]\G′ and S_{σ} := G′ [ v]. Since G′ is convex in G (by (v)), S_{σ} is a simplex. We shall prove that F^{∗} can be extended by a new factor B_{σ} ⊂ G [ C_{σ} → S_{σ}], in contradiction to the maximality of F^{∗} in F.

To spare the reader the task of monitoring over all stages of the proof what happens if σ = 0 (i.e. if G′ = ∅), let us deal with this case first.

Let S be a maximally prime subgraph of G containing v. If S is unattached, set B_{σ} := S. If S is attached, to the component C of G\S say, then (C, S) is an inaccessible side of G. Let x be any neighbour of v in C. Then { v } has the prime extension ({ v, x }, { vx }) into C, so by Lemma 6 we can select as B_{σ} an unattached maximally prime subgraph of G containing v.

In either case we have v ^{∈} B_{σ} and therefore B_{σ} ⊂ H_{σ} (notice that (C_{σ}, ∅) ^{∈} H_{σ}^{1} and hence H_{σ}^{1} ≠ ∅, because B_{σ} exists as chosen). Hence B_{σ} is as desired.

Let us from now on assume that σ > 0. In order to comply with (v), our desired new factor B_{σ} must be chosen in such a way that G′ ∪ B_{σ} is convex. Since S_{σ} is attached to C_{σ} and C_{σ} is connected, this means that B_{σ} will have to contain the entire S_{σ} (cf. [ 4, Corollary 1.7 (iii) ]), i.e. S_{σ} will be the simplex of attachment of B_{σ}. Our first objective therefore is to show that S_{σ} is contained in B_{λ} for some λ < σ, so that B_{σ} ∩ G|_{σ} can satisfy (iv).

The following proposition (A) serves this purpose.

(A) S_{σ} ⊂ B_{λ}, for some λ < σ.

The idea underlying the proof of (A) is central to the whole proof of Theorem 1: using conditions (vi) and (vii), we show that S_{σ} was created in at most finitely many steps, unlike the simplex S that caused problems in our examples H^{1} and H^{2} in [ 4, Section 4 ]. More precisely, we shall prove that Λ(S_{σ}) is finite; then (A) will be immediate from [ 4, Corollary 1.7 (i) ]. Suppose Λ(S_{σ}) is infinite, and let S ⊃ S_{σ} be a maximal simplex in G′.

We first show that S must be unattached in G′. Suppose S is attached in G′, say to the component C′ of G′\S. Then (G [ C′ → S]\S , S) is a side in G. Applying (†) to this side with C_{σ} assuming the role of C′ in (†), we may deduce that S_{σ} has a prime extension B into G [ C′ → S]\S (but note that B is not necessarily a subgraph of G′).

Let us find a vertex x ^{∈} C′ that is simplicially close to every vertex of S_{σ} (Fig. 3). If B ∩ C′ ≠ ∅, we simply pick x ^{∈} B ∩ C′. Suppose now that B ∩ C′ = ∅. Then B\S ⊂ G\G′; notice that, by the convexity of G′ in G, G [ C′ → S] contains no vertices from components of G′\S other than C′. Since G′ is convex, G′ [ B\S] is a simplex. As B is prime, this means that G′ [ B\S] does not separate any vertices of B, so G′ [ B\S] ⊃ S_{σ}. But G′ [ B\S] also has a vertex in C′, since, by definition of B, S does not separate B\S from C′. Choosing x ^{∈} G′ [ B\S] ∩ C′, we have therefore again found a vertex x ^{∈} C′ that is close to every vertex of S_{σ}.

Having shown that C′ contains a vertex x which is simplicially close to every vertex of S_{σ}, we may infer by [ 4, Proposition 1.4 ], that S_{σ} has a prime extension into C′: the convex hull of S_{σ} ∪ { x } in G′. This, however, contradicts [ 4, Theorem 3.2 (iii) ] (put S′ := S_{σ}). Therefore S is unattached in G′.

Having shown that S is unattached in G′, we may deduce that the position of S in G′ is as stated in [ 4, Theorem 3.2 (iv) ]; let Λ ⊂ Λ(S) and (C_{λ})_{λ^{∈}Λ} be as provided, and let λ′ denote λ(C_{λ}) (for λ ^{∈} Λ).

Let us prove that { k(λ′) | λ^{∈} Λ } is not bounded by any n^{∈} ℕ. Suppose { k(λ′) | λ^{∈} Λ } is bounded. Then H_{λ′} ≠ ∅ for every λ ^{∈} Λ, and for some k ^{∈} ℕ there are infinitely many λ ^{∈} Λ with k(λ′) = k. We can therefore find λ_{1}, λ_{2} ^{∈} Λ satisfying λ_{1} < λ_{2}, k(λ′_{1}) = k(λ′_{2}) = k, and either H_{λ′_{1}}^{1} = H_{λ′_{2}}^{1} = ∅ or H_{λ′_{1}}^{1}, H_{λ′_{2}}^{1} ≠ ∅. Notice that condition (c) of [ 4, Theorem 3.2 (iv) ] and our assumption that λ_{1} < λ_{2} imply λ′_{1} ≤ λ_{1} ^{∈} Λ(S|_{λ_{2}}) = Λ(S_{λ′_{2}}), so λ′_{1} < λ′_{2}.

Let us write B^{i} for B_{λ′_{i}} (i = 1, 2). We shall prove that B^{2} was eligible at G|_{λ′_{1}}, and use this to deduce that the choice of B^{1} contradicts (vi). To see that B^{2} was eligible at G|_{λ′_{1}}, note that B^{2} ∩ G|_{λ′_{1}} = S|_{λ_{1}} = S_{λ′_{1}}, which is by (S4) contained in some B_{λ}, λ < λ′_{1}. Thus all we have to check is that G|_{λ′_{1}} ∪ B^{2} is convex in G. This, however, follows from Lemma 8 (put H := G|_{λ′_{1}} and B_{i} := B^{i}; Fig. 4).

For the proof that the choice of B^{1} was inconsistent with condition (vi), suppose first that H_{λ′_{1}}^{1} = H_{λ′_{2}}^{1} = ∅. Then H_{λ′_{1}}^{2} and H_{λ′_{2}}^{2} are non-empty, so by (vii) there are sides (C^{i}, S^{i}) ^{∈} H_{λ′_{i}}^{2} satisfying S^{i} ⊂ B^{i} and v_{k} ^{∈} C^{i} (and B^{i} ∩ C^{i} = ∅, because H_{λ′_{i}}^{1} = ∅), i = 1, 2.

Since v_{k} ^{∈} C^{1} ∩ C^{2}, we have C^{1} ∩ C^{2} ≠ ∅. Moreover, as (C^{2}, S^{2}) is still undefused at G|_{λ′_{2}},

S^{1} ∩ C^{2} ⊂ B^{1} ∩ C^{2} = ∅ .

Therefore (C^{2}, S^{2}) ≤ (C^{1}, S^{1}) by Lemma 3 (ii). Since B^{1} defuses (C^{1}, S^{1}) but not (C^{2}, S^{2}), these sides are not identical, so even (C^{2}, S^{2}) < (C^{1}, S^{1}). Applying Lemma 3 (iii), we thus obtain

B^{2} ∩ C^{1} ⊃ S^{2} ∩ C^{1} ≠ ∅ ,

so B^{2} is an extension of S_{λ′_{1}} ⊂ S^{1} into C^{1}. Since B^{2} is eligible at G|_{λ′_{1}}, this implies that (C^{1}, S^{1}) is 1-defusable at G|_{λ′_{1}}. Hence H_{λ′_{1}}^{1} ≠ ∅, contrary to our assumption.

Suppose now that neither of H_{λ′_{1}}^{1}, H_{λ′_{2}}^{1} is empty. Then by (vi) there are sides (C^{i}, S^{i})^{∈} H_{λ_{i}}^{1} that satisfy B^{i} ∩ C^{i} ≠ ∅, i = 1, 2. Since B^{2} is eligible at G|_{λ′_{1}}, (C^{2}, S^{2}) is 1-defusable at G|_{λ′_{1}}, so (C^{2}, S^{2}) ^{∈} H_{λ′_{1}}^{1}. On the other hand, (C^{2}, S^{2}) is still undefused at G|_{λ′_{2}}, so B^{1} ⊄ G [ C^{2} → S^{2} ]. Therefore B^{1} ⊄ H_{λ′_{1}}, contradicting (vi). This completes the proof that { k(λ′) | λ ^{∈} Λ } is unbounded in ℕ.

Let us now finish our proof of (A). Suppose first that S is attached in G, say to the component C of G\S. (If S = S_{σ}, C may coincide with C_{σ}.) Since S is unattached in G′ and G′ is convex, we have C ∩ G′ = ∅. Hence, for each λ ^{∈} Λ, S [ C_{λ}] has an unattached and maximally prime extension into C (by (†) and Lemma 6), which is eligible at G|_{λ′} by Lemma 8 (as earlier). Hence (C, S) ^{∈} H_{λ′} and consequently k(λ′) ≤ min { i | v_{i} ^{∈} C } for every λ ^{∈} Λ, contrary to the unboundedness of k(λ′) established above.

Suppose now that S is unattached in G. Then S itself is eligible at G|_{λ′} for every λ ^{∈} Λ [ 4, Corollary 1.9 ]. Since S contains S_{σ} and therefore defuses (C_{σ}, S_{σ}), this implies that k(λ′) ≤ min { i | v_{i} ^{∈} C_{σ} }, again contradicting the unboundedness of k(λ′). This completes the proof of (A).

As an immediate consequence of (A) let us note that

(B) S_{σ} is attached in G′.

Let us now determine a subgraph B_{σ} that extends F^{∗} and contradicts the assumed maximality of F^{∗} in F. All graphs we consider as candidates for the role of B_{σ} will be maximally prime and unattached extensions of S_{σ} into C_{σ}. Then the only conditions we shall have to verify for ⋃_{λ≤σ} B_{λ} will be (vi) and (vii); notice that (iv) will hold by (A), and (v) will be satisfied because B_{σ} and G′ are convex and S_{σ} separates B_{σ}\S_{σ} from G′\S_{σ} in G.

If H_{σ} = ∅, (vi)–(vii) are trivially satisfied, so we may take B_{σ} to be any unattached maximally prime extension of S_{σ} into C_{σ} (by (B), (†) and Lemma 7).

If H_{σ}^{1} = ∅ but H_{σ}^{2} ≠ ∅, the existence of a suitable B_{σ} is guaranteed by the definition of H_{σ}^{2}. (We remark that any undefused (C, S) with v ^{∈} C must satisfy S ≠ S_{σ} (by (A)) and hence (C, S) < (C_{σ}, S_{σ}), so B_{σ} (⊃ S) will be a subgraph of G [ C_{σ} → S_{σ}].)

Suppose now that H_{σ}^{1} ≠ ∅. In our search for B_{σ} we now have to ensure that B_{σ} meets the rather strict condition (vi), i.e. that B_{σ} intersects with C for every 1-defusable side (C, S). This will require some work, which is the price we now pay for having been able to use the full strength of (vi) in the proof of (A).

Since v ^{∈} C for every (C, S) ^{∈} H_{σ}^{1} , Lemma 3 (ii) gives

(C) (C, S) ≤ (C′, S′) iff S′ ∩ C = ∅ , for all (C, S), (C′, S′) ^{∈} H_{σ}^{1} .

Similarly, we have (C, S) < (C_{σ}, S_{σ}) for all (C, S)^{∈} H_{σ}^{1}, and consequently G [ C →S] ⊂ G [ C_{σ} → S_{σ}]. (The inequality is strict, because since (C_{σ}, S_{σ}) is ‘2-defused’ by some B_{λ}, λ < σ, (C_{σ}, S_{σ}) is not in H_{σ}.) Moreover,

(D) S ∩ G′ = S_{σ} for every (C, S) ^{∈} H_{σ}^{1} ,

that is, every such S contains the entire S_{σ}. To see this, recall that any eligible B ⊂ G [ C_{σ} → S_{σ}] must contain S_{σ}. Since (C, S) is 1-defusable at G|_{σ}, we have S_{σ} ⊂ B ⊂ G [ C → S] for some such B, giving S_{σ} ⊂ S by C ∩ G′ = ∅.

In order to determine B_{σ}, it will be convenient to find a prime and convex subgraph B^{∗} of G that satisfies B^{∗} ∩ C_{σ} ≠ ∅, B^{∗} ⊃ S_{σ}, v /^{∈} B^{∗} and S^{∗} ⊅ S_{σ}, where S^{∗} := B^{∗} [ v] (Fig. 5).

If H_{σ}^{1} contains an unbounded descending chain C (i.e. one that is maximal in H_{σ}^{1} with respect to extension and has no minimal element), it is not difficult to find such a graph B^{∗}. As in the proof of Lemma 6, we let

H^{−} := ⋂_{(C,S)^{∈}C} G [ C → S] ,  D^{−} := ⋂_{(C,S)^{∈}C} C ,  S^{−} := H^{−}\D^{−}.

Moreover, we let C^{∗} be the component of D^{−} containing v, and put S^{∗} := S^{−} [ C^{∗}]. By (D), we have S_{σ} ⊂ S for every (C, S) ^{∈} C, and hence S^{−} ⊃ S_{σ}. As in the proof of Lemma 6 it is shown that S^{−} is a simplex, and that S^{∗} ∩ C ≠ ∅ for each (C, S) ^{∈} C, giving S^{−} ∩ C_{σ} ≠ ∅. Since C^{∗} ⊂ D^{−}, we further have (C^{∗}, S^{∗}) ≤ (C, S) for every (C, S) ^{∈} C. As C is by assumption unbounded in H_{σ}^{1} , this means that (C^{∗}, S^{∗}) /^{∈} H_{σ}^{1} . Hence S^{∗} ⊅ S_{σ}, because otherwise (C^{∗}, S^{∗}) would be 1-defusable at G|_{σ} (by (†) and Lemma 7), implying (C^{∗}, S^{∗}) ^{∈} H_{σ}^{1} . Therefore B^{∗} := S^{−} is as required.

Let us now assume that every descending chain in H_{σ}^{1} is bounded. Let H_{σ}^{0} denote the set of all minimal elements of H_{σ}^{1}. Then

(E) S is maximally prime in G, for every (C, S) ^{∈} H_{σ}^{0}.

To prove (E), it suffices to show that every (C, S) ^{∈} H_{σ}^{0} is inaccessible (Lemma 2). Suppose (C, S) ^{∈} H_{σ}^{0} is accessible, and let \overline{S} be a maximal prime extension of S into C.

If v /^{∈} \overline{S}, we may assume that S^{∗} := \overline{S} [ v] contains S_{σ}, for otherwise we can put B^{∗} := \overline{S} and have B^{∗} as desired. (\overline{S} is convex, because it is maximally prime in G.) But assuming S^{∗} ⊃ S_{σ} and putting C^{∗} := G [ v → \overline{S}]\\overline{S}, we find that (C^{∗}, S^{∗}) is a side which is 1-defusable at G|_{σ} (by (†) and Lemma 7) and satisfies (C^{∗}, S^{∗}) < (C, S). This contradicts the minimality of (C, S) in H_{σ}^{1}.

If v ^{∈} \overline{S} on the other hand, we can easily find a new factor B_{σ} extending F^{∗}. If \overline{S} is unattached in G, we put B_{σ} := \overline{S}. If \overline{S} is attached, however, say to \overline{C}, then \overline{C} ∩ C_{σ} ≠ ∅ and hence \overline{C} ⊂ C_{σ}, because \overline{S} ⊃ S ⊃ S_{σ} and v has a neighbour in \overline{C}. We can therefore use (†) (and Lemmas 4,6) to select as B_{σ} an unattached maximally prime extension of \overline{S} [ S_{σ} ∪ \{ v \}] into \overline{C}, once more exploiting the fact that \{ v \} has a trivial prime extension into \overline{C} because it has a neighbour in \overline{C}. Then, in either case, v ^{∈} B_{σ} implies that B_{σ} ⊂ H_{σ}, so (B_{λ})_{λ≤σ} satisfies (i)–(vii). This completes the proof of (E).

If H_{σ}^{0} consists of a single element (C, S), we let B_{σ} be any unattached maximally prime extension of S_{σ} into C (by (D), (†) and Lemma 6). Then B_{σ} ⊂ G [ C → S] = H_{σ}, so ⋃_{λ≤σ} B_{λ} satisfies (i)–(vii), contradicting the maximality of F^{∗}. As H_{σ}^{1} is by assumption non-empty, H_{σ}^{0} therefore has at least two elements (C, S) and (C′, S′).

By (C), we have S′ ∩ C ≠ ∅ as well as S ∩ C′ ≠ ∅, so C contains S′\S and C′ contains S\S′ (and these graphs are not empty). Let H be the convex hull of S ∪ S′ in G, and define B^{∗} the way T′ was defined in the proof of Lemma 6. Then B^{∗} is a simplex that satisfies B^{∗} ∩ C ≠ ∅ and B^{∗} ∩ C′ ≠ ∅ (and hence B^{∗} ∩ C_{σ} ≠ ∅), contains S ∩ S′ (and therefore S_{σ}; cf. (D)), separates S\B^{∗} (≠ ∅) from S′\B^{∗} (≠ ∅) in G, and is attached to D := G [ S → B^{∗}]\B^{∗} as well as to D′ := G [ S′ → B^{∗}]\B^{∗}.

If v ^{∈} B^{∗}, we simply let B_{σ} be an unattached maximally prime extension of B^{∗} into D or D′ (by (†) and Lemma 7). Then B_{σ} ⊂ H_{σ} because v ^{∈} B_{σ}, so (B_{λ})_{λ≤σ} conforms to (i)–(vii), contradicting the maximality of F^{∗}.

Therefore v /^{∈} B^{∗}; let C^{∗} denote the component of G\B^{∗} containing v. Since D and D′ are also components of G\B^{∗}, we may assume without loss of generality that C^{∗} ≠ D. Then S ∩ C^{∗} = ∅, which implies (C^{∗}, S^{∗}) < (C, S) by Lemma 3 (ii) (with S^{∗} := B^{∗} [ v], as usual). But (C, S) is minimal in H_{σ}^{1}, so this means that (C^{∗}, S^{∗}) /^{∈} H_{σ}^{1}, and therefore S^{∗} ⊅ S_{σ} (by (†) and Lemma 7). Hence B^{∗} is as desired.

Let us now finish our proof by using the properties of B^{∗} and S^{∗} to find an additional factor B_{σ} ⊂ H_{σ}. Notice that S^{∗} is a simplex, because B^{∗} is convex. Put C^{∗} := G [ v → B^{∗}]\B^{∗} , and let (C, S) be any element of H_{σ}^{1}. Since S contains S_{σ} but G [ C^{∗} → S^{∗}] does not, S ∩ C^{∗} must be empty. Hence (C^{∗}, S^{∗}) < (C, S), by v ^{∈} C^{∗} ∩ C and Lemma 3 (ii). Thus S^{∗} ∩ C ≠ ∅ for every (C, S) ^{∈} H_{σ}^{1}, giving B^{∗} ⊂ H_{σ}.

If B^{∗} is unattached in G, we let B_{σ} := B^{∗} and are done (B_{σ} will be maximally prime by [ 4, Proposition 1.8 ]); suppose therefore that B^{∗} is attached in G, say to the component D^{∗} of G\B^{∗}. Since B^{∗} is convex, this means that B^{∗} is a simplex, and (D^{∗}, B^{∗}) is a side in G. Since B^{∗} is not attached to C^{∗}, clearly D^{∗} ∩ C^{∗} = ∅. Furthermore, we have (D^{∗}, B^{∗}) < (C_{σ}, S_{σ}) because B^{∗} ⊃ S_{σ} and B^{∗} ∩ C_{σ} ≠ ∅ (Lemma 3 (iii)), giving D^{∗} ⊂ C_{σ}. Hence, D^{∗} ∩(C^{∗} ∪G′) = ∅. Let B_{σ} be an unattached maximally prime extension of S_{σ} ∪S^{∗} into D^{∗} (by (†) and Lemma 7). Then B_{σ} ∩ C ⊃ S^{∗} ∩ C ≠ ∅ for every (C, S) ^{∈} H_{σ}^{1} , giving B_{σ} ⊂ H_{σ}. Hence ⋃_{λ≤σ} B_{λ} satisfies (i)–(vii), contrary to the assumed maximality of F^{∗}.

This completes the proof of Theorem 1.

As an immediate corollary of the proof of Theorem 1 we see that, for any countable graph G that admits a simplicial tree-decomposition into primes, not only every prime factor of G is maximally prime, minimally convex and unattached [ 4, Theorem 1.10 ], but conversely any subgraph of G with these properties is a factor in some simplicial tree-decomposition of G into primes:

Corollary 9. Let G be a countable graph admitting a prime decomposition, and let B ⊂ G. Then the following statements are equivalent.

(i) B is minimally convex and unattached in G; (ii) B is maximally prime and unattached in G; (iii) B is a factor in some prime decomposition of G.

Proof. As (i) and (ii) are equivalent by [ 4, Proposition 1.8 ], all we have to show is that (ii) implies (iii). By assumption G has a prime decomposition, so G satisfies (†). Choose an enumeration of V (G), beginning with a vertex in B. Then F = (B) is a family that satisfies conditions (i)–(vii) from the proof of Theorem 1, so F can be extended to a prime decomposition of G. □

2. Two Examples

As the examples discussed in part one of this paper already indicated, a main difficulty that had to be overcome in the proof of Theorem 1 was the possible existence of inaccessible sides in the graph G considered: the algorithm used to construct a prime decomposition of G had to detect and defuse any inaccessible side (C, S) before S was completely covered by factors B_{λ} ⊄ G [ C → S]. The way this was achieved was by ensuring that the set of inaccessible sides defused by each new factor was in a rather strong sense maximal (condition (vi)), and the difficulty in proving the theorem lay in showing that such new factors can indeed always be found.

Bearing this in mind, it may not be too surprising that the proof of Theorem 1 becomes substantially easier if all the graphs considered have at most countably many simplices with inaccessible sides, which can then be defused according to a much simpler priority rule. On the other hand, it is not clear at first sight whether a countable graph can have uncountably many such simplices at all, i.e. whether such a simplification of the proof would perhaps still cover all countable graphs.

In this section we shall answer this question in the negative by giving an example of a graph that satisfies (†), and in which uncountably many simplices have an inaccessible side. The graph we construct will also provide some illustration for the proof of Theorem 1.

The second graph exhibited in this section is an uncountable variation of the first. It still satisfies (†), but it has no prime decomposition. This second example therefore shows that Theorem 1 cannot be extended to uncountable graphs, and is in this respect best possible.

Let us construct a graph T_{0} as follows. Let the vertices of T_{0} be all finite 0-1 sequences, i.e. let V (T_{0}) := { 0, 1 }^{[ω]}, and join (a_{0}, …, a_{n}) to (b_{0}, …, b_{m}) whenever n < m and a_{i} = b_{i} for i = 0, …, n. Thus if we write α < β for α, β ^{∈} { 0, 1 }^{[ω]} iff β is an extension of α, then T is simply the comparability graph of its vertex set.

Let T_{1} be the graph obtained from T_{0} by adding all edges of the form (a_{0}, …, a_{n−1}, 0)(a_{0}, …, a_{n−1}, 1, 0, …, 0), i.e. by additionally joining (a_{0}, …, a_{n}) to (b_{0}, …, b_{m}) whenever n ≤ m, a_{i} = b_{i} for i = 0, …, n − 1, a_{n} = 0, b_{n} = 1, and b_{n+1} = … = b_{m} = 0 (Fig. 6).

T_{1} has maximally prime subgraphs of two different types. First, there are the simplices spanned by those maximal sets V of pairwise comparable vertices that satisfy

∀ i ^{∈} ℕ : ∃ (a_{0}, …, a_{n}) ^{∈} V : (n ≥ i and a_{n} = 1) .

Every such simplex S has an inaccessible side (C, S), where C is the component of T_{1}\S spanned by all vertices of T_{1}\S that are lexicographically smaller than some vertex in S (or ‘left’ of S in Fig. 6). It is also clear that T_{1} has 2^{ℵ_{0}} of these simplices.

The maximally prime subgraphs of the other type are extensions (by one additional vertex) of simplices spanned by those maximal sets of pairwise comparable vertices that are not among the vertex sets of the simplices with inaccessible sides defined above. Each of these simplices S has the property that

∃ i ^{∈} ℕ : ∀ (a_{0}, …, a_{n}) ^{∈} V (S) : (i ≤ j ≤ n ⇒ a_{j} = 0) .

The additional vertex x(S) is (a_{0}, …, a_{n−1}, 0) if (a_{0}, …, a_{n}) ^{∈} S and

n = max { i ^{∈} ℕ | (a_{0}, …, a_{i}) ^{∈} S and a_{i} = 1 };

so S is in fact uniquely determined by x(S), and S_{x} := T_{1} [ S ∪ { x(S) }] is an unattached and hence maximally prime simplex in T_{1}.

There is only one maximally prime subgraph of T_{1} that is not of one of these two types. This is the unattached simplex S_{0} := T_{1} [ ∅, (0), (00), (000), …].

It is not difficult to check that T_{1} satisfies (†), and that T_{1} has a prime decomposition whose factors are simplices of the form S_{x} and possibly S_{0}.

Let us now turn to the second of the two examples in this section. Define the graph T_{2} from T_{0} by adding to it new vertices v(S), one for each maximal simplex S in T_{0}, joining v(S) to every vertex of S for each S. T_{2} has order 2^{ℵ_{0}} (recall that the maximal simplices of T_{0} are precisely those subgraphs of T_{0} that are spanned by maximal sets of ‘pairwise comparable’ vertices, so there are 2^{ℵ_{0}} of them), and the set S of maximally prime subgraphs of T_{2} is precisely the set of all subgraphs of the form T_{2} [ S ∪ { v(S) }].

Since every attached simplex of T_{2} can be extended to a simplex of the form T_{2} [ S ∪ { v(S) }] in each of its sides, no side in T_{2} is inaccessible. Hence T_{2} satisfies (†).

However, T_{2} has no prime decomposition. To see this, let us suppose that (B_{λ})_{λ<σ} is a prime decomposition of T_{2}. Since prime factors are always maximally prime and the only maximally prime subgraph of T_{2} containing the vertex v(S) is T_{2} [ S ∪ { v(S) }], the set { B_{λ} | λ < σ } of factors coincides with S. Hence σ is uncountable. But T_{2} [ S ∪ { v(S) }] is also the only maximally prime subgraph of T_{2} containing S. Since by assumption every μ < σ is such that S_{μ} ⊂ B_{λ} for some λ < μ (S4), this means that, whenever v ^{∈} T_{2}\T_{0}, S_{λ(v)} cannot contain the entire S, i.e. λ(s) = λ(v) for some s ^{∈} S. Therefore Λ(T_{0}) = σ, which contradicts the countability of T_{0}.

3. Simplicial Minors

The purpose of this section is to announce another characterization of the countable graphs that have simplicial tree-decompositions into primes. The characterization is based on Theorem 1, and it will be pesented in detail in a forthcoming paper [ 6 ].

The basic idea of this result is to show that there are essentially only two different non-decomposable graphs: similarly to Kuratowski’s classical theorem on planar graphs, it characterizes the decomposable graphs in terms of two forbidden minors, the usual notion of a minor being slightly restricted to match the purpose. Both forbidden minors are variations of Halin’s graph H_{0} (see [ 4 ]).

Let G, G′ be graphs, and let f : V (G) → V (G′) be surjective. Halin [ 10 ] defines f to be 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′). Notice that homomorphisms between graphs map simplices to simplices.

If H ⊂ G and H′ ⊂ G′ are induced subgraphs and f : V (G) → V (G′) is a homomorphism, 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. Conversely, f|_{H} is a contractive homomorphism from H onto f(H) if H is convex in G and f is contractive, in which case f(H) is also convex in G′.

Let us call a contractive homomorphism f from G onto G′ 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′.

Simplicial homomorphisms are well compatible with simplicial decompositions: they map minimally convex subgraphs to minimally convex subgraphs and maximally prime subgraphs to maximally prime subgraphs or attached simplices, and the restriction of a simplicial homomorphism to a convex subgraph is again a simplicial homomorphism.

A graph H′ is often called a minor of a graph 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.

It is not difficult to show that if G_{1} ≻_{s} G_{2} and G_{2} ≻_{s} G_{3}, then G_{1} ≻_{s} G_{3}. Or in other words, if H is a set of graphs, then the graph property

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

is closed under taking simplicial minors.

In order to be characterized in this way, the class of decomposable graphs must of course match this feature, i.e. simplicial minors of decomposable graphs must again be decomposable. And indeed, it can be shown that this is so: 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.

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 since simplicial minors of decomposable graphs are again decomposable, we even have 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. We are therefore left with the challenge to find a minimal such H′.

Let H_{1} be the graph obtained from H_{0} by contracting the path Q to one vertex q, and let H_{2} be obtained from H_{1} by joining up all vertices inside P, thus turning P into a simplex (Fig. 7). Neither H_{1} nor H_{2} has a prime decomposition (by Theorem 1; put C′ := { q }), and neither of the two graphs is a simplicial minor of the other. It will be shown in [ 6 ] that H′ = { H_{1}, H_{2} } solves the above problem:

Theorem. [ 6 ] 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.

A similar characterization will be obtained for the countable graphs that admit a tree-decomposition into primes.

Figure 7 22

References

1. R. Diestel, On the problem of finding small subdivision and homomorphism bases for classes of countable graphs, Discrete Math. 55 (1985), 21–33.

2. R. Diestel, A separation property of planar triangulations, J. Graph Theory , to appear.

3. R. Diestel, Simplicial decompositions of graphs—some uniqueness results, J. Combin. Theory B , to appear.

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

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

6. R. Diestel, Simplicial minors and decompositions of graphs, submitted.

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

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

9. R. Halin, Zur Klassifikation der endlichen Graphen nach H. Hadwiger und K. Wagner, Math. Ann. 172 (1967), 46–78.

10. R. Halin, Graphentheorie II, Wissenschaftliche Buchgesellschaft, Darmstadt 1981.

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

12. R. Halin, Simplicial decompositions and triangulated graphs, in: (B. Bollobás, ed.) Graph Theory and Combinatorics, Academic Press, London 1984.

13. N. Robertson and P. D. Seymour, Graph minors I–XVIII, J. Combin. Theory B , to appear.

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