SIMPLICIAL TREE-DECOMPOSITIONS OF INFINITE GRAPHS I

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

Abstract. This paper is intended as an introduction to the theory of simplicial decompositions of graphs. It presents, in a unified way, new results as well as some basic old ones (with new proofs). Its main result is a structure theorem for infinite graphs with a simplicial tree-decomposition into primes. The existence and uniqueness of such prime decompositions will be investigated in two subsequent papers.

A simplicial decomposition of a graph is the recursively defined analogue to writing it as the union of two induced subgraphs overlapping in a complete graph, a ‘simplex’. These decompositions have successfully been applied in various branches of graph theory and elsewhere; a survey of such applications can be found in [ 2 ]. In a series of three papers we shall here consider the more theoretical aspects of simplicial decompositions. An overview of theoretical results (including those obtained in this series) and open problems concerning simplicial decompositions is given in [ 1 ].

If a graph has a simplicial decomposition into primes, i.e. into subgraphs that cannot be decomposed further, then these primes are essentially its smallest convex subgraphs. Unlike finite graphs, an infinite graph does not necessarily have a simplicial decomposition into primes, and if it does, this decomposition will not necessarily be unique.

It is one of the oldest problems in the theory of simplicial decompositions to characterize the graphs that have a prime decomposition. In part two of this series [ 4 ] we shall obtain such a characterization for the simplicial decompositions of the most typical and common type, named ‘tree-decompositions’ after the shape in which their factors are arranged. (These simplicial tree-decompositions served as the prototype for the tree-decom-positions recently introduced by Robertson and Seymour [ 13 ]). Our characterization of the graphs decomposable in this way is by a condition on the position of their separating simplices, a condition arising naturally from the structure of the known non-decomposable graphs. Part three of the series [ 5 ] deals with the uniqueness of simplicial tree-decompo-sitions into primes: we shall prove that the uniqueness known for prime decompositions of finite graphs extends to simplicial tree-decompositions of infinite graphs, provided only that these are minimal in a certain very natural sense.

In this paper, part one of the series, we give an introduction to simplicial decompositions and simplicial tree-decompositions, prove a basic theorem concerning their structure, and discuss some approaches to the problem of the existence of prime decompositions.

We begin with some terminology. Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family F = (B_{λ})_{λ<σ} is called a simplicial tree-decomposition of G (Fig. 1) 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 λ < μ (μ < σ). If F satisfies (S1)–(S3) but not necessarily (S4), F is called a simplicial decomposition of G. If F satisfies (S1) and (S4), F is called a tree-decomposition of G. (This definition of a tree-decomposition is equivalent to, and in some cases more convenient than the original definition given by Robertson and Seymour [ 13 ]).

FIGURE 1.

If F = (B_{λ})_{λ<σ} is any fixed family of induced subgraphs of G satisfying (S1), and if H ⊂ G, x ^{∈} V (G) and μ ≤ σ, we denote by λ(H) the minimal λ for which B_{λ} ∩ H ≠ ∅, abbreviate λ({ x }) to λ(x), set Λ(H) := { λ(x) | x ^{∈} V (H) }, and write H|_{μ} := ⋃_{λ<μ} B_{λ} ∩ H. Thus if we view F as a growing organism, then λ(H) indicates the stage of growth at which the first vertex of H appears, and H|_{μ} is the portion of H that is present just before the vertices x with λ(x) = μ appear, the vertices of B_{μ}\G|_{μ}.

If F satisfies (S1) and (S2), e.g. if F is a simplicial decomposition, then every G|_{μ} is an induced subgraph of G; for if x, y ^{∈} V (G|_{μ}), xy ^{∈} E(G)\E(G|_{μ}), and τ < σ is minimal with xy ^{∈} E(B_{τ}) (τ exists by (S1)), then xy must already be an edge of G|_{τ} (by (S2) and μ ≤ τ), contrary to the choice of τ. Since H|_{μ} = ⋃_{λ<μ} B_{λ} ∩ H = ( ⋃_{λ<μ} B_{λ}) ∩ H = G|_{μ} ∩ H, this implies that, more generally, every H|_{μ} is an induced subgraph of H, i.e. that H|_{μ} = H[{ x ^{∈} V (H) | λ(x) < μ }]. With slight abuse of terminology, the subgraphs G|_{μ} will sometimes be referred to as the ‘partial decompositions’ of G.

A graph will be called prime (with respect to simplicial tree-decompositions) if it has no simplicial tree-decomposition into more that one subgraph. A prime induced subgraph of G is maximally prime in G if it is not properly contained in any prime induced subgraph of G. (As a general rule, all prime subgraphs we consider shall be induced.) A simplicial tree-decomposition in which all members are prime is a simplicial tree-decomposition into primes, or a prime decomposition. B ⊂ G is a factor of G if B is a member of some simplicial tree-decomposition of G.

Occasionally we shall use the above terms with respect to other kinds of decomposition too, in particular with respect to simplicial decompositions that are not necessarily treedecompositions. Confusion should not arise, especially as the graphs that are prime with respect to simplicial tree-decompositions coincide with those that are prime with respect to general simplicial decompositions (see Section 1).

We shall usually refer to complete graphs as simplices, as is the custom in the field. The graphs S_{μ} = G|_{μ} ∩ B_{μ} in (S2) will be called simplices of attachment.

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′. More generally we shall say that H is attached (in G) if H is attached to some component of G\H; otherwise H is unattached (in G).

An example of attached graphs we shall frequently encounter is that of a minimal relative 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 or a minimal relative separator in G 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 that contains contains 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. We remark that the simplex S in a side (C, S) may be empty, in which case C is simply a component of G. C however, being a component, is never empty.

If (C, S) is a side in G, S′ ⊂ S, and X is an induced subgraph of G satisfying X ⊃ S′ and X ∩ C ≠ ∅, we shall call X an extension of S′ into C. Since S separates C from the rest of G, X ⊂ G is a maximal prime extension of S′ into C iff X contains S′, meets C, and is maximally prime in G.

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. When the underlying graph G is fixed, we shall usally abbreviate G [ X → Y ] ∩ Y to Y [ X]. Thus, Y [ X] is the subgraph of Y 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 equivalent 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 X ⊂ G or X ⊂ V (G), the intersection H of all convex subgraphs of G containing X is again convex in G; H will be called the convex hull of X in G.

Since factors in a simplicial tree-decomposition of G are by definition induced subgraphs, vertices belonging to a common prime factor are never separated by a simplex in G (cf. Corollary 1.2). Conversely we shall call vertices of G (simplicially) close in G if no simplex separates them in G, no matter whether G has a prime decomposition or not. Notice that if H is a convex subgraph of G, then vertices x, y ^{∈} V (H) are close in H iff they are close in G.

For X ⊂ G, the subgraph of G induced by all vertices of G that are simplicially close to every vertex of X will be called the simplicial neighbourhood of X in G. We remark that the simplicial neighbourhood of any subgraph of G is convex in G [ 3 ].

And finally, if Λ is a set of ordinals, we use ‘sup^{+}Λ’ to denote min{ μ | ∀ λ^{∈} Λ : λ < μ }.

1. Simplicial Decompositions

The notion of simplicial decompositions of graphs goes back to a paper of K. Wagner in 1937 [ 14 ]. Wagner introduced these decompositions in order to prove his now well known theorem on the equivalence of the 4-Colour-Conjecture and Hadwiger’s Conjecture for n = 5. His idea was to consider all (maximal finite) graphs not contracting to a complete graph of order 5, ‘simplicially’ decompose them into primes, and show that the primes—and hence all these graphs—can be 4-coloured (assuming the 4CC).

Since then, the evolving theory of simplicial decompositions owes most of its results to R. Halin. Halin not only used it successfully in a number of applications similar to Wagner’s—among other things he characterized several graph properties defined in terms of forbidden minors by determining their ‘homomorphism base’, see e.g. [ 9 ]—but also began to investigate simplicial decompositions for their own sake.

One reason why simplicial decompositions have turned out to be a rather interesting subject in their own right is that the prime factors of a graph and, to a lesser extent, its simplices of attachment, are subgraphs distinguished by very natural properties—and therefore of interest quite apart from their role in decompositions (cf. Theorem 1.9). Yet whereas the primes of a finite graph can be found simply by repeated ‘de-composition’ along separating simplices, this process need not terminate for infinite graphs: hence Halin’s inductive definition of simplicial decompositions ‘from below’, as quoted at the beginning of Section 0. And indeed, it turned out that there exist infinite graphs which have no simplicial decomposition into primes; the first example was again given by Halin [ 8 ]. However, as his main theorem in [ 8 ] Halin proved that all graphs without infinite simplices have prime decompositions. The resulting problem to determine which graphs admit a simplicial decomposition into primes has since stood unresolved. Its most extensive study yet is found in Dirac [ 7 ].

Another open problem may be mentioned at this point: it is still unknown which infinite graphs admit a simplicial decomposition into finite factors. This problem may well be related to that of characterizing the graphs that admit a reduced simplicial tree-decom-position into primes; see [ 5 ].

We now give a summary of the most basic properties of simplicial decompositions. Our first proposition is also the most important one: factors and partial decomposi-

tions in simplicial decompositions are convex subgraphs. This fact accounts for much of the naturalness of simplicial decompositions and simplicial tree-decompositions, and it is a central element in the proof of almost every theorem on the subject.

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

Proof. For the convexity proof of G|_{μ}, let P be any induced path in G with endvertices in G|_{μ}. We have to show that P ⊂ G|_{μ}. Since P is finite, Λ(P) has a maximum λ^{∗}. Then P ⊂ G|_{λ^{∗}+1}, because G|_{λ^{∗}+1} is an induced subgraph of G. Now if λ^{∗} ≥ μ, then P has two non-consecutive vertices in S_{λ^{∗}}, and therefore a chord. This contradicts our assumption that P is induced in G. Hence λ^{∗} < μ, giving P ⊂ G|_{λ^{∗}+1} ⊂ G|_{μ} as claimed.

Likewise, any induced path P ⊂ G joining vertices of B_{μ} is contained in G|_{μ+1}. Moreover, P cannot meet G|_{μ}\S_{μ}, because then P would have two non-consecutive vertices in S_{μ}. Hence P ⊂ B_{μ}, so B_{μ} is convex. □

The convexity of G|_{μ+1} implies in particular that S_{μ} separates G, because S_{μ} separates B_{μ}\S_{μ} from G|_{μ}\S_{μ} in G|_{μ+1}. Therefore any graph that has a simplicial decomposition into more than one factor also has a simplicial decomposition into exactly two factors, and hence a non-trivial simplicial tree-decomposition. Or in other words, a graph is prime with respect to simplicial tree-decompositions iff it is prime with respect to simplicial decompositions, as remarked earlier.

Furthermore,

Corollary 1.2. A graph G is prime iff it contains no separating simplex.

Proof. If G has a separating simplex, we can clearly decompose G into at least two factors. Conversely if (B_{λ})_{λ<σ} is a simplicial tree-decomposition of G and σ ≥ 2, then S_{1} is a separating simplex of G|_{2}. By Proposition 1.1, S_{1} also separates G. □

By a straightforward application of Zorn’s Lemma, Corollary 1.2 implies that every prime subgraph (and in particular, every vertex) of a graph G is contained in some maximally prime subgraph of G.

Corollary 1.3. [ 10 ] If B is prime and S ⫋ B is a simplex, then S is attached in B.

Proof. Let C be the unique component of B\S, and suppose that S is not attached to C. Then S \ S [ C] ≠ ∅, and S [ C] separates S \ S [ C] from C in B. □

As an example for Corollary 1.3, consider a simplex of attachment S_{μ} in a prime decomposition of a graph G. Since S_{μ} is properly contained in B_{μ} (S3) as well as in some B_{λ}, λ < μ (S4/3), S_{μ} is attached to both B_{μ}\S_{μ} and G|_{μ}\S_{μ}.

Proposition 1.4. If the vertices of X ⊂ G are pairwise simplicially close in G, then the convex hull H of X in G is prime.

Proof. Suppose that H is not prime, and let S ⊂ H be a separating simplex in H (by Corollary 1.2). By assumption S does not separate any vertices of X in G, so, by the convexity of H in G, S does not separate any vertices of X in H either. We therefore have X ⊂ H [ C ∪ S] for some component C of H\S. Thus H [ C ∪ S] is a convex proper subgraph of H containing X, contrary to the definition of H. □

Corollary 1.5. [ 10 ] (i) Maximally prime subgraphs are convex.

(ii) A maximally prime and attached subgraph is a simplex. □

Observe that, as another consequence of Proposition 1.4, the simplicial neighbourhood of a prime induced subgraph B of G is precisely the union of all prime induced subgraphs B′ of G containing B.

The following lemma is a rather typical consequence of the convexity of partial decompositions G|_{τ}. Although simple, the lemma reflects a fundamental feature of simplicial decompositions.

Lemma 1.6. Let (B_{λ})_{λ<σ} be a simplicial decomposition of a graph G, S ⊂ G a simplex, s ^{∈} V (S), λ ^{∈} Λ(S), and C a component of G\S. Then the following assertions hold:

(i) S_{λ} ⊃ S|_{λ} (and therefore B_{λ} ⊃ S|_{λ+1}) ; (ii) if λ(C) < λ(s) and s ^{∈} S [ C], then S_{λ(s)} ∩ C ≠ ∅; (iii) S [ C]|_{λ(C)} ⊂ S_{λ(C)}.

Proof. To see (i), note that if s′ ^{∈} S|_{λ}\S_{λ} and s′′ ^{∈} S is such that λ(s′′) = λ, then s′ and s′′ are adjacent in G but not in G|_{λ+1}, a contradiction.

In order to show (ii), suppose that S_{λ(s)} ∩ C = ∅. Then S_{λ(s)} separates s from C|_{λ(s)} in G|_{λ(s)+1}; note that C|_{λ(s)} ≠ ∅, because λ(C) < λ(s). But since s ^{∈} S [ C], no subgraph of G that avoids C can separate s from C|_{λ(s)} in G. This contradicts the convexity of G|_{λ(s)+1}.

For (iii), note that if S [ C]|_{λ(C)}\S_{λ(C)} ≠ ∅, say s ^{∈} S [ C]|_{λ(C)} \ S_{λ(C)}, then S_{λ(C)} separates s from B_{λ(C)} ∩ C in G|_{λ(C)+1}. But no subgraph of G avoiding C separates s from any vertex of C in G, because S [ C] is attached to C. This violates the convexity of G|_{λ(C)+1}. □

Let us note the following immediate consequences of Lemma 1.6.

Corollary 1.7. Let (B_{λ})_{λ<σ} be a simplicial decomposition of G and S ⊂ G a simplex. Then the following holds, for any s ^{∈} V (S) and any side (C, S) in G:

(i) if Λ(S) has a maximum λ^{∗}, then S ⊂ B_{λ^{∗}}; (ii) if λ(C) ≤ λ(s), then B_{λ(s)} ∩ C ≠ ∅; (iii) if S ⊂ G|_{λ(C)} and B_{λ(C)} is prime, then S = S_{λ(C)}. □

If (B_{λ})_{λ<σ} is a simplicial decomposition into primes, Lemma 1.6 has a substantial impact on the possible relative positions of S and the components C of G\S with λ(C) < sup^{+}Λ(S [ C]). For if C is such a component, it is not difficult to show (using Lemma 1.6 (i)–(ii) and Corollary 1.3) that S [ C] must be of the form S|_{μ}, with μ = sup^{+}Λ(S [ C]). Hence, B_{λ} meets C precisely for those λ ^{∈} Λ(S) that satisfy λ(C) ≤ λ < sup^{+}Λ(S [ C]) (again by Lemma 1.6 (ii) and Corollary 1.3). Or more intuitively, from the moment a component C is born, each subsequent s ^{∈} S has a vertex of C in its simplex of attachment, until λ(s) exceeds Λ(S [ C]). Since no prime factor can have vertices in more than one component of G\S, we thereby obtain a 1–1 correspondence between these C’s and pairwise disjoint segments of Λ(S). See Theorem 3.2 for details.

Let us call H ⊂ G minimally convex in G if H is convex in G and H is not the union of two proper subgraphs H′, H′′ ⊂ H that are convex in G (or, equivalently, in H). It is not difficult to show that a convex graph H ⊂ G is minimally convex in G iff every convex proper subgraph of H is a simplex and H is not isomorphic to a K_{−}^{n}, a complete graph from which one edge has been deleted.

Proposition 1.8. [ 3 ] 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.

Let us note the following useful consequence of the implication (ii)→(iii) in Proposition 1.8:

Corollary 1.9. Unattached simplices are maximally prime. □

Conversely, maximally prime simplices can be attached (see Section 4 for an example), but only if they are infinite (Halin [ 8 ]; we shall reobtain this result in [ 4, Corollary 5 ]). In fact, the possibility of the existence of maximally prime but attached simplices has been the main obstacle on the road to a comprehensive characterization of the graphs that have a simplicial decomposition into primes.

When one tries to find a prime decomposition for a given graph, or to prove constructively that some given condition is sufficient for the existence of a prime decomposition, as we shall do in [ 4 ], one must have an idea among which subgraphs to look for potential factors. Fortunately, these subgraphs are determined fairly precisely:

Theorem 1.10.

(i) All factors in simplicial decompositions are unattached.

(ii) Prime factors in simplicial decompositions are minimally convex and maximally prime.

Proof. Let (B_{λ})_{λ<σ} be a simplicial decomposition of a graph G and suppose that B_{μ} is attached in G, say to the component C of G\B_{μ}. Since B_{μ} is convex (Proposition 1.1) and attached, it must be a simplex; thus (C, B_{μ}) is a side in G. Therefore λ(C) > μ by Corollary 1.7 (ii), so B_{μ} [ C]|_{λ(C)} = B_{μ} [ C] = B_{μ}. Hence B_{μ} ⊂ S_{λ(C)} by Lemma 1.6 (iii), which violates (S3). Therefore B_{μ} is unattached in G.

By Propositions 1.1 and 1.8 this further implies that if B_{μ} is prime, then B_{μ} is minimally convex and maximally prime. □

And conversely:

Theorem 1.11. [ 10/3 ] Suppose that G has a simplicial decomposition F = (B_{λ})_{λ<σ} into primes, and let B be an induced subgraph of G.

(i) If B is maximally prime in G and is not an infinite simplex, then B is a factor in F.

(ii) If B is minimally convex in G and is not a simplex, then B is a factor in F.

We remark that the exclusion of infinite simplices in Theorem 1.11 (i) is unavoidable: if S is an infinite simplex in G, then S may be a factor in one prime decomposition of G and not in another; an example will be given in [ 5 ].

2. Tree-decompositions

Recall that a family F = (B_{λ})_{λ<σ} of induced subgraphs of a graph G is a tree-decomposi-tion of G if F satisfies conditions (S1) and (S4). This term, first introduced by Robertson and Seymour [ 13 ], has its origin in the following observation.

Let F = (B_{λ})_{λ<σ} be a simplicial decomposition of a finite graph G. Then F is even a simplicial tree-decomposition of G, i.e. F satisfies (S4): for each μ < σ, Λ(S_{μ}) has a maximal element τ(μ) < μ, and S_{μ} is contained in B_{τ(μ)} (Corollary 1.7 (i)). It is clear that the graph T_{F} defined by

V (T_{F}) := { B_{λ} | λ < σ }

and

E(T_{F}) := { B_{μ}B_{τ(μ)} | μ < σ }

is a tree.

This ‘tree-shape’ in simplicial decompositions of finite graphs is perhaps their most prominent feature, and it has far-reaching implications; see [ 13 ].

Conversely, the sets Λ(S_{μ}) are finite in any tree-decomposition, and therefore have maximal elements τ(μ):

Proposition 2.1. Let (B_{λ})_{λ<σ} be a tree-decomposition of a graph G, and let μ < σ. Then Λ(B_{μ}) is a subset of the finite set { μ, τ(μ), τ(τ(μ)), …, 0 }, where τ(ν) denotes the least λ < ν for which S_{ν} ⊂ B_{λ} (ν < σ).

Proof. The set { μ, τ(μ), τ(τ(μ)), …, 0 } is finite, because its elements form a strictly descending sequence of ordinals. The assertion follows by induction on μ. □

With every tree-decomposition F we can therefore associate a tree T_{F}, just as with finite simplicial decompositions.

The following lemma asserts that we can rearrange the factors in any countably infinite tree-decomposition into a tree-decomposition of order type ω, without changing their attachment graphs S_{μ}:

Lemma 2.2. Let F = (B_{λ})_{λ<σ} be a tree-decomposition of a graph G, and suppose that ω < σ < ω_{1}. Then G has a tree-decomposition F′ = (B′_{λ})_{λ<ω} with { B′_{λ} | λ < ω } = { B_{λ} | λ < σ }, such that S′_{μ} := B′_{μ} ∩ ⋃_{λ<μ} B′_{λ} = S_{ν} whenever B′_{μ} = B_{ν} (μ < ω, ν < σ).

Proof. For any two factors B, B̃ of F let us write B̃ ≤ B if B̃ lies on the unique B_{0}–B path in T_{F}. Let k : V (T_{F}) → ℕ be an enumeration of the vertices of T_{F}, i.e. of the factors B ^{∈} F.

Put B′_{0} := B_{0} and, having defined B′_{0}, …, B′_{λ}, let B′_{λ+1} be one of those remaining factors B ^{∈} F for which

{ B̃ ^{∈} V (T_{F}) | B̃ < B } ⊂ { B′_{0}, …, B′_{λ} };

moreover, choose B′_{λ+1} among these B such that k(B) is minimal. In other words, we reconstruct T_{F} vertex by vertex, choosing each new vertex B with minimal k(B) provided that the subgraph of T_{F} induced by the selected vertices remains connected. Since { B̃ | B̃ < B } and k(B) are finite for each B, every factor from F is selected into F′ after finitely many steps. Hence, F′ is a tree-decomposition of G.

Let us now show that B′_{μ} = B_{ν} implies S′_{μ} = S_{ν}. By construction of F′, B_{τ(ν)} gets selected before B_{ν}, so clearly

S′_{μ} ⊃ B′_{μ} ∩ B_{τ(ν)}
= B_{ν} ∩ B_{τ(ν)}
= S_{ν} .

To see the reverse inclusion S′_{μ} ⊂ S_{ν}, recall first that, by Proposition 2.1, λ ^{∈} Λ(S_{ρ}) implies B_{λ} < B_{ρ} (for all ρ < σ). Now suppose that S′_{μ} ⊄ S_{ν}, and let x ^{∈} S′_{μ}\S_{ν}. Then x ^{∈} B_{ν}\S_{ν}, so λ(x) = ν. Since x ^{∈} S′_{μ}, there exists λ < μ with x ^{∈} B′_{λ}, say B′_{λ} = B_{ρ}. Clearly ρ ≠ ν, so λ(x) = ν means that x ^{∈} S_{ρ}. Thus ν ^{∈} Λ(S_{ρ}), and therefore B′_{μ} = B_{ν} < B_{ρ} = B′_{λ}. But this contradicts the definition of F′, since B′_{λ} is selected before B′_{μ} (by λ < μ). □

3. Simplicial Tree-decompositions

Let us first note a consequence of Lemma 2.2. Simplicial tree-decompositions are distinguished among general simplicial decompositions of countable graphs not only by their typical shape, but also by the fact that the order of their factors is without loss of generality given by a simple enumeration:

Theorem 3.1. Let G be a countable graph, and let F = (B_{λ})_{λ<σ} be a simpicial decomposition of G.

(i) If σ ≤ ω, then F is a tree-decomposition.

(ii) If F is a tree-decomposition, then either σ < ω, or G has a simplicial tree-decom-position F′ = (B′_{λ})_{λ<ω} satisfying { B′_{λ} | λ < ω } = { B_{λ} | λ < σ }.

Proof. (i) Suppose that σ ≤ ω, and let S = S_{μ} be given, μ < σ. Since Λ(S) is finite, it has a maximal element λ^{∗}; by Corollary 1.7 (i), λ^{∗} is such that S ⊂ B_{λ^{∗}}.

(ii) If σ ≤ ω, there is nothing to show. If σ > ω, let F′ be as provided by Lemma 2.2. Since { S′_{λ} | λ < ω } = { S_{λ} | λ < σ }, F′ is again a simplicial decomposition. □

In proving the following structure theorem for simplicial tree-decompositions we take up the thread from our observations following Lemma 1.6: the theorem gives a detailed description of the possible positions of a maximal simplex in a graph that has a simplicial tree-decomposition into primes.

Theorem 3.2. Let G be a graph, F = (B_{λ})_{λ<σ} a simplicial tree-decomposition of G into primes, and S ⊂ G a maximal simplex. Then the following assertions hold.

(i) If Λ(S) is finite and S is unattached in G, then S is a factor in F.

(ii) If Λ(S) is finite and S is attached in G, then S has prime extensions into every component C of G\S to which it is attached. These prime extensions can be chosen to be factors in F.

(iii) If Λ(S) is infinite and S is attached in G, then Λ(S) has order type ω and S is maximally prime in G. Furthermore, S is attached to a unique component C of G\S, which satisfies λ(C) < sup^{+}Λ(S). A subsimplex S′ ⊂ S has a prime extension into C if and only if Λ(S′) is finite; if such an extension exists, it can be chosen to be a factor in F.

(iv) If Λ(S) is infinite and S is unattached in G, then Λ(S) has order type ω, S is maximally prime in G, and there exist an infinite set Λ ⊂ Λ(S) and a family (C_{λ})_{λ^{∈}Λ} of components C_{λ} of G\S such that the following holds for every λ ^{∈} Λ (with λ′ := λ(C_{λ}) and λ^{+} denoting the successor of λ in Λ) :

(a) For every μ ^{∈} Λ(S), B_{μ} ⊂ G [ C_{λ} → S] if and only if λ ≤ μ < λ^{+} ;

(b) S [ C_{λ}] = S|_{λ^{+}} ;

(c) λ′ ≤ λ, and S_{λ′} = S|_{λ};

(d) S = ⋃_{λ^{∈}Λ} S_{λ′} . (Figure 2) Moreover, if C is a component of G\S and S [ C] ⫋ S, then Λ(S [ C]) is finite and S [ C] has a prime extension B ^{∈} F into C.

Proof. In order to prove (i) and (ii), we first assume that Λ(S) is finite; let λ^{∗} := max Λ(S). By Corollary 1.7 (i), we have S ⊂ B_{λ^{∗}}. If S is unattached in G, then even S = B_{λ^{∗}} by Corollary 1.3, giving (i).

Turning now to (ii), let us suppose that S is attached to some component C of G\S. If λ(C) ≤ λ^{∗}, then B_{λ^{∗}} is a prime extension of S into C by Corollary 1.7 (ii). But if λ(C) > λ^{∗} then S ⊂ G|_{λ(C)}, so S = S|_{λ(C)} (Corollary 1.7 (iii)). Thus in this case, B_{λ(C)} is a prime extension of S into C.

To prove (iii) and (iv), let us from now on assume that Λ(S) is infinite. By Proposition 2.1, Λ(B_{λ}) is finite for every λ < σ. Hence, Λ(S) must have order type ω (by Lemma 1.6 (i)), and S /^{∈} F.

Since no factor in F can be properly contained in S, we have B_{λ}\S ≠ ∅ for each λ^{∈} Λ(S). As B_{λ} is prime and therefore not separated by S, there exists a unique component C_{λ} of G\S containing B_{λ}\S. Then B_{λ} ⊂ G [ C → S] iff C = C_{λ}, for every component C of G\S.

To prove (iii), let C be any component of G\S to which S is attached. By Corollary 1.7 (iii), Proposition 2.1 and our assumption that Λ(S) is infinite, C satisfies λ(C) < sup^{+}Λ(S). Therefore C = C_{λ} for almost all λ ^{∈} Λ(S) (by Corollary 1.7 (ii)), which implies that C is unique.

Let S′ ⊂ S be given. If Λ(S′) is finite, there exists μ ^{∈} Λ(S) with μ ≥ sup^{+}Λ(S′) and μ > λ(C); by Lemma 1.6 (i)–(ii), B_{μ} is a prime extension of S′ into C. Suppose now that Λ(S′) is infinite. Then sup^{+}Λ(S′) = sup^{+}Λ(S). We have to show that S′ has no prime extension into C, i.e. that each vertex of C is separated from some vertex of S′ by a simplex. Let x ^{∈} C be given. Suppose first that λ(x) < sup^{+}Λ(S). If x is contained in S_{λ} for almost all λ ^{∈} Λ(S′), then x is adjacent to every s ^{∈} S (by Lemma 1.6 (i)), contradicting our assumption that S is a maximal simplex in G. But otherwise there exists λ ^{∈} Λ(S′) such that λ > λ(x) and x /^{∈} S_{λ}; then S_{λ} separates x from every s ^{∈} S′ with λ(s) = λ. Similarly if λ(x) ≥ sup^{+}Λ(S), then S′\S_{λ(x)} ≠ ∅ because Λ(S_{λ(x)}) is finite, so S_{λ(x)} separates x from some s ^{∈} S′. Therefore S′ has no prime extension into C.

It remains to show that S is maximally prime in G. Since S must be attached to B\S whenever S ⫋ B and B is prime (Corollary 1.3), any proper prime extension of S must be one into C. As shown above, such an extension does not exist (put S′ := S). This completes the proof of (iii).

Let us now assume that S is unattached in G, and prove (iv). S is maximally prime by Corollary 1.9. Let

C := { C ⊂ G | C = C_{λ} for some λ ^{∈} Λ(S) } ,

and for each C ^{∈} C, let λ_{C} denote the minimal λ ^{∈} Λ(S) satisfying C_{λ} = C. We claim that

Λ := { λ ^{∈} Λ(S) | λ = λ_{C} for some C ^{∈} C }

satisfies conditions (a)–(d). For each λ ^{∈} Λ we set λ′ := λ(C_{λ}) and let λ^{+} denote the successor of λ in Λ if it exists; until we have established that a successor does exist for every λ ^{∈} Λ, i.e., that Λ is unbounded in Λ(S), we provisionally put λ^{+} := sup^{+}Λ(S) if λ is maximal in Λ.

For a proof of (a), let λ^{∈} Λ and μ^{∈} Λ(S) be given. Suppose first that B_{μ} ⊂ G [ C_{λ} →S], i.e. that C_{μ} = C_{λ}. We have to show that λ ≤ μ < λ^{+}. By definition of Λ, the fact that C_{μ} = C_{λ} implies that λ ≤ μ. To show that μ < λ^{+}, suppose μ ≥ λ^{+}, and let s^{+} be any vertex of S with λ(s^{+}) = λ^{+}. Then s^{+} ^{∈} B_{μ} (Lemma 1.6 (i)). Since by assumption B_{μ} ∩ C_{λ} ≠ ∅, this means that s^{+} ^{∈} S [ C_{λ}], because B_{μ} is prime. Hence B_{λ^{+}} meets C_{λ} as well as C_{λ^{+}} (Lemma 1.6 (ii)), a contradiction.

To prove the other direction of (a), we now assume that λ ≤ μ < λ^{+} and show that C_{μ} = C_{λ}. Let ν be the element of Λ satisfying C_{μ} = C_{ν}. Then ν ≤ μ < λ^{+} by definition of Λ, giving ν ≤ λ. On the other hand, we have μ < ν^{+} by the first direction of (a) and hence λ ≤ μ < ν^{+}, giving λ ≤ ν. Therefore ν = λ as required, completing the proof of (a).

For (b), recall that any s ^{∈} S [ C_{λ}] \ S|_{λ^{+}} would be such that B_{λ(s)} ∩ C_{λ} ≠ ∅ (Lemma 1.6 (ii)) and hence B_{λ(s)} ⊂ G [ C_{λ} → S]; since this contradicts (a), we have S [ C_{λ}] ⊂ S|_{λ^{+}}. To prove the reverse inclusion, i.e. that S [ C_{λ}] ⊃ S|_{λ^{+}}, let s be an arbitrary vertex of S|_{λ^{+}}. If λ(s) < λ, then s ^{∈} S|_{λ} ⊂ S_{λ} ⊂ B_{λ} ⊂ G [ C_{λ} → S] (Lemma 1.6 (i)), so s ^{∈} S [ C_{λ}]. If λ(s) ≥ λ on the other hand, then λ ≤ λ(s) < λ^{+}; therefore s ^{∈} B_{λ(s)} ⊂ G [ C_{λ} → S] by (a), so again s ^{∈} S [ C_{λ}]. Hence S [ C_{λ}] = S|_{λ^{+}}, completing the proof of (b).

Let us note at this point that Λ has no maximal element, and is therefore unbounded in Λ(S): if λ ^{∈} Λ is maximal in Λ, then S [ C_{λ}] = S|_{λ^{+}} = S by (b) (recall that λ^{+} = sup^{+}Λ(S) in this case), contradicting our assumption that S is unattached in G.

For a proof of (c), notice first that λ′ = λ(C_{λ}) ≤ λ by definition of λ(C_{λ}), because B_{λ} ∩ C_{λ} ≠ ∅. Let us apply Corollary 1.7 (iii) to show that S_{λ′} = S|_{λ}. By (b), S|_{λ} is attached to C_{λ} in G, so all we have to verify is that S|_{λ} ⊂ G|_{λ′}, i.e. that μ < λ′ for all μ ^{∈} Λ(S) with μ < λ. But if μ ^{∈} Λ(S) satisfies λ′ ≤ μ < λ, then B_{μ} ∩ C_{λ} ≠ ∅ and hence C_{μ} = C_{λ} (by (b), Corollary 1.7 (ii) and the definition of λ′), which contradicts the choice of λ as the minimal ordinal in Λ(S) with this property. Assertion (c) thus follows by Corollary 1.7 (iii) as claimed.

Finally, (d) follows from (c) and the fact that Λ is unbounded in Λ(S). This completes the proof of (iv).

It remains to show that whenever C is a component of G\S and S [ C] ⫋ S, then Λ(S [ C]) is finite and S [ C] has a prime extension B ^{∈} F into C. If λ(C) ≥ sup^{+}Λ(S [ C]), this follows from Lemma 1.6 (iii) and Proposition 2.1. Suppose therefore that λ(C) < sup^{+}Λ(S [ C]).

We first show that Λ(S [ C]) is finite. In cases (i) and (ii) this is clear. For cases (iii) and (iv) notice that if Λ(S [ C]) is infinite, then for every s ^{∈} S there exists μ ^{∈} Λ(S [ C]) such that μ > λ(s) as well as μ > λ(C). Then s ^{∈} S_{μ} (Lemma 1.6 (i)) and S_{μ} ∩ C ≠ ∅ (Lemma 1.6 (ii)), so s has a neighbour in C. Thus S is attached to C, contrary to our assumption that S [ C] ⫋ S. Therefore Λ(S [ C]) is finite.

Let λ^{∗} := max Λ(S [ C]). Then λ(C) ≤ λ^{∗}, since by assumption λ(C) < sup^{+}Λ(S [ C]). By Corollary 1.7 (i)–(ii) applied to S [ C], B_{λ^{∗}} is a prime extension of S [ C] into C. □

4. The Problem of the Existence of Prime Decompositions

In this section we consider the problem of which graphs admit a simplicial tree-decompo-sition into primes. In order to find a criterion that characterizes these graphs, we first look at a few examples.

Halin’s example [ 8 ] of a graph that has no prime decomposition is essentially the following. Let S = S [ s_{1}, s_{2}, …] be an infinite simplex and P = x_{1}x_{2} …, Q = y_{1}y_{2} … one-way infinite paths, and let H_{0} be the graph obtained from the disjoint union of S, P and Q by drawing the edges x_{i}s_{j} and y_{i}s_{j} for all i, j ^{∈} ℕ, i ≥ j (Fig. 3). It will soon become clear why H_{0} has no prime decomposition.

Let H^{1} be the graph obtained from H_{0} by deleting the edges of P, and let H^{2} be obtained from H^{1} by contracting Q to a single vertex q and deleting the edges qs_{i} for even i (Fig. 4). The maximally prime subgraphs of H^{1} are B′_{i} := H^{1} [ x_{i}, s_{1}, …, s_{i}] (i ^{∈} ℕ), B′′_{i} := H^{1} [ y_{i}, y_{i+1}, s_{1}, …, s_{i}] (i ^{∈} ℕ) and S, and the maximally prime subgraphs of H^{2} are B′_{i} := H^{2} [ x_{i}, s_{1}, …, s_{i}] (i ^{∈} ℕ), S and B′′ := H^{2} [ q → S] (cf. Theorem 1.10).

Let us try to arrange these subgraphs into prime decompositions (B_{λ})_{λ<σ} of H^{1} and H^{2}, putting B_{0} := B′_{1} say, B_{1} := B′_{2}, and so on. At H^{1}|_{ω} (or H^{2}|_{ω}, respectively) we get stuck. In the case of H^{2} the problem is obvious: the only factor left is B′′, but we cannot add it, because its simplex of attachment would be S′′ := S ∩ B′′, which is not contained in any of the previous factors (cf. (S4)). Yet even in the case of H^{1} we cannot add any new factor: for adding B′′_{i} as B_{ω} would violate the convexity required for H^{1}|_{ω+1} (Proposition 1.1), because S_{ω} = S [ s_{1}, …, s_{i}] would not separate B′′_{i}\S from S\B′′_{i} in G. Or in slightly more general terms, any additional factor B ⊂ H^{1} [ Q → S] complying with the convexity requirement for H^{1}|_{ω+1} would have to contain the entire S, because Q is connected and S is attached to Q (cf. Corollary 1.7 (iii)).

Figure 4

Thus any condition on a graph G guaranteeing that any family F = (B_{λ})_{λ<τ} of maximally prime subgraphs of G can be extended to a prime decomposition of G, provided only that F complies with (S2)–(S4) and every G|_{μ} is convex (μ ≤ τ), should imply

Figure 5

(∗) Whenever (C, S) is a side in G, S has a prime extension into C.

For graphs with at most finite simplices, (∗) is indeed true—see [ 4, Corollary 5 ]. But in general (∗) is already too strict to cover all graphs that have a prime decomposition: H^{1}, for example, fails to satisfy (∗), but it has a prime decomposition: all we have to do in order to avoid getting stuck is to ‘defuse’ the side (Q, S) before S is completed, i.e. to select one of the B′′_{j}’s after only finitely many B′_{i}’s. (For example, H^{1} admits the decomposition (B′′_{1}, B′′_{2}, … B′_{1}, B′_{2}, …).) In the case of H^{2}, the problem is resolved similarly: in order to ‘defuse’ the side ({ q }, S′′), we simply have to select S as a factor (after at most finitely many B′_{i}’s), and we will be able to attach B′′ at the end.

How, then, can we weaken (∗) so as to accomodate all graphs admitting a prime decomposition, yet keep it strong enough to guarantee the existence of a prime decomposition when it is satisfied?

Let us call a side (C, S) of G accessible if S has a prime extension into C, and inaccessible otherwise. Using these terms, (∗) simply says that G has no inaccessible sides. But if this is not necessary for G to admit a prime decomposition, what is? Our examples suggest—and it is indeed not difficult to prove—that the following condition is necessary for G to admit a prime decomposition: (∗∗) If (C, S) is an inaccessible side of S in G, then (C, S) is the only side of S in G. But this condition is not sufficient for the existence of a prime decomposition.

To see this, consider the graph H^{3} obtained from H^{2} by restoring the edges of P (Fig. 5). The maximally prime and unattached subgraphs of H^{3} are the simplices B′′ := H^{3} [ q → S] and B′_{i} := H^{3} [ x_{i}, x_{i+1}, s_{1}, …, s_{i}] (i ^{∈} ℕ). It is easily checked that the only inaccessible side in H^{3} is (P, S), so H^{3} satisfies (∗∗). Now suppose, for contradiction, that H^{3} has a prime decomposition F = (B_{λ})_{λ<σ}. If λ(q) = 0, i.e. if B′′ = B_{0}, then S_{1} = S′′ := S ∩ B′′ by Corollary 1.7 (iii) (consider the side (H^{3} [ P → S′′]\S′′, S′′)), which contradicts the fact that none of the B′_{i}’s contains S′′. Therefore λ(q) > 0. By (S4), B′′ is preceded by at most finitely many B′_{i}’s in F, so S has a vertex s with λ(s) = λ(q). Therefore B_{λ(q)} ∩ P ≠ ∅ by Corollary 1.7 (ii), contradicting the fact that B_{λ(q)} = B′′.

Let us recapitulate. We have studied two conditions concerning the positions of simplices in a graph G. The first, (∗), implies that G has a prime decomposition, but there are graphs that fail to satisfy (∗) while still admitting a prime decomposition. The second, (∗∗), is satisfied by every graph G that has a prime decomposition, but we have constructed a graph without one that also satisfies (∗∗). Moreover, (∗∗) is a direct weakening of (∗), that is, (∗) implies (∗∗).

Thus any condition characterizing the graphs that admit a prime decomposition must imply (∗∗) and follow from (∗). In [ 4 ], we shall find such a condition and thereby obtain a first characterization of the countable graphs that have a simplicial tree-decomposition into primes.