SIMPLICIAL TREE-DECOMPOSITIONS OF INFINITE GRAPHS III The Uniqueness of Prime Decompositions

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

Abstract. In this last of three papers on simplicial tree-decompositions of graphs we investigate the extent to which prime factors in such decompositions are unique, or depend on the decomposition chosen. A simple example shows that a prime decomposition of a graph may have superfluous factors, the omission of which leaves a set of factors that can be rearranged into another decomposition of the same graph. As our main result we show that this possibility is the only way in which prime decompositions can vary: we prove that all prime decompositions of a countable graph without such superfluous members have the same set of factors. We also obtain a characterization theorem which identifies these factors among similar subgraphs by their position within the graph considered, independently of their role in any decomposition.

The material presented in this paper rests on concepts and results developed in [ 4 ]; in particular, the reader will benefit from familiarity with [ 4, Theorem 3.2 ]. The paper does not depend on [ 5 ], but its results are complementary and in that sense related to those obtained in [ 5 ].

Let G be a graph, σ > 0 an ordinal, and let B_{λ} be an induced subgraph of G for every λ < σ. The family (B_{λ})_{λ<σ} is called a simplicial tree-decomposition of G if

(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 graph is prime if and only if it contains no separating simplex [ 4, Corollary 1.2 ]. A simplicial tree-decomposition in which all factors are prime will be called a simplicial treedecomposition into primes, or a prime decomposition.

1. The Uniqueness Problem

The purpose of this paper is to explore to what extent simplicial tree-decompositions into primes are unique.

The extreme case of such uniqueness would be that any two prime decompositions of a graph consisted of the same set of factors, and these were necessarily arranged in the same order. The latter, however, is almost never true: even in cases when the factors in any two prime decompositions of a certain graph are the same, their order is likely to vary greatly. We shall not consider the order aspect of uniqueness in this paper.

A third aspect of uniqueness in prime decompositions, in a sense a weakening of the unattainable uniqueness of the order of factors, is the question of uniqueness for simplices of attachment. And, remarkably, we do have complete uniqueness here, even in cases where the set of factors is not unique: a simplex S contained in a graph G is a simplex of attachment in any prime decomposition of G if and only if S is a minimal relative separator in G, i.e. an induced subgraph minimally separating some two vertices of G (see Proposition 3).

It thus remains to investigate to what extent the factors in a prime decomposition of a graph vary with the decomposition chosen, and this will be the subject of this paper.

As an example, let us consider the graph H^{2} introduced in [ 4 ]. H^{2} consists of an infinite simplex S = S [ s_{1}, s_{2}, …], independent vertices x_{1}, x_{2}, … joined to S by the edges x_{i}s_{j} for i, j ^{∈} ℕ, i ≥ j, and another vertex q joined to all s_{i} with odd i [ 4, Figure 4 ]. The maximally prime subgraphs of H^{2} (and therefore its potential prime factors, cf. [ 4, Theorem 1.10 ]) are B′_{i} := H^{2} [ x_{i}, s_{1}, …, s_{i}] (i ^{∈} ℕ), S and B′′ := H^{2} [ q → S].

Let us first look at the graph H^{2}\{ q }. This graph has two different prime decompositions,

F_{1} := (S, B′_{1}, B′_{2}, …)

and

F_{2} := (B′_{1}, B′_{2}, …).

Notice that after dropping S from F_{1} and thus obtaining F_{2}, we cannot omit any more factors: unlike S in F_{1}, none of the B′_{i}’s in F_{2} is covered by the remaining factors in F_{2}, so each factor in F_{2} is indispensable for F_{2} to cover the graph H^{2}\{ q }.

Let us now consider the graph H^{2} itself. H^{2} admits the prime decomposition

F_{3} := (S, B′_{1}, B′_{2}, …, B′′).

Again, S is covered by the other factors of F_{3}. But this time S must not be omitted: the family

F_{4} := (B′_{1}, B′_{2}, …, B′′)

satisfies (S1)–(S3), but it violates (S4), because B′′ ∩ ⋃_{i=1,2,...} B′_{i} = S [ s_{1}, s_{3}, …] is not contained in any of the factors B′_{i}. Thus S is indispensable as a factor in F_{3}, not because it is needed to cover H^{2}, but because it serves as an ‘interface’ between B′′ and the other factors in F_{3}.

This will be made more precise in the next section. We shall prove that the above two reasons for being indispensable as a factor are the only possible ones, and that any prime decomposition from which all ‘dispensable’ factors have been removed, consists of a unique set of factors.

2. Reduced Decompositions

Let G be a graph, F = (B_{λ})_{λ<σ} a simplicial tree-decomposition of G, and μ < σ. We shall call B_{μ} dispensable in F if G has a simplicial tree-decomposition F′ = (B′_{λ})_{λ<σ′} that satisfies { B′_{λ} | λ < σ′ } ⊂ { B_{λ} | μ ≠ λ < σ }; otherwise B_{μ} is indispensable in F. F will be called a reduced simplicial tree-decomposition if every B_{μ}, μ < σ, is indispensable in F.

Let us call a subgraph H of G weakly attached in G if every vertex of H has a neighbour in G\H. If H is not weakly attached in G, we shall call H strongly unattached in G. It is clear that attached subgraphs are also weakly attached, and that strongly unattached subgraphs are unattached.

Suppose finally that H is an induced subgraph of G, and that C is the set of all components of G\H. H will be called an interface in G if H is weakly attached in G and

∃ C, C′ ^{∈} C : ∀ C′′ ^{∈} C : H [ C] ∪ H [ C′] ⊄ H [ C′′]

(recall that H [ C] = G [ C → H] ∩ H). Notice that interfaces are by definition unattached but never strongly unattached.

Before we use these terms to tackle our uniqueness problem, let us note that as far as non-complete or finite factors are concerned, all prime decompositions of a given graph G agree anyhow: a non-complete or finite subgraph of G is a prime factor in any given decomposition iff it is maximally prime in G [ 4, Theorems 1.10/1.11 ]. (Thus in particular, all prime decompositions into finite graphs are reduced.)

For reduced decompositions, we are now able to supply the missing characterization for infinite complete subgraphs: the following theorem implies that a simplex S ⊂ G is a factor in any reduced prime decomposition of G if and only if S is strongly unattached or an interface in G.

Theorem 1. Let G be a countable graph, F = (B_{λ})_{λ<σ} a simplicial tree-decomposition of G into primes, and S ⊂ G a simplex.

(i) If S is strongly unattached or an interface in G, then S is a factor in F.

(ii) If S is an indispensable factor in F, then S is strongly unattached or an interface in G.

Theorem 1 is the main result of this paper. We reserve its proof for Section 3, and first take a look at its consequences.

Corollary 2. Let G be a countable graph, F = (B_{λ})_{λ<σ} a simplicial tree-decomposition of G into primes, and μ < σ. B_{μ} is indispensable in F if and only if B_{μ} is either strongly unattached or an interface in G.

Proof. Suppose first that B_{μ} is strongly unattached or an interface in G. If B_{μ} is a simplex, then any prime decomposition F′ = (B′_{λ})_{λ<σ′} of G with

{ B′_{λ} | λ < σ′ } ⊂ { B_{λ} | μ ≠ λ < σ }

violates Theorem 1 (i), so B_{μ} is indispensable in F. If B_{μ} is not a simplex, then B_{μ} is indispensable in F by [ 4, Theorems 1.10/1.11 ].

Suppose now that B_{μ} is indispensable in F. If B_{μ} is a simplex, it is strongly unattached or an interface by Theorem 1 (ii); it cannot be both, because an interface is by definition never strongly unattached. Assume now that B_{μ} is not a simplex, let v, v′ ^{∈} V (B_{μ}) be non-adjacent, and suppose that B_{μ} is weakly attached in G. Then G\B_{μ} has components C, C′ with v ^{∈} B_{μ} [ C] and v′ ^{∈} B_{μ} [ C′]. But no component C′′ of G\B_{μ} can be such that B_{μ} [ C] ∪ B_{μ} [ C′] ⊂ B_{μ} [ C′′] and hence v, v′ ^{∈} B_{μ} [ C′′]: for since B_{μ} is convex, this would imply that vv′ ^{∈} E(B_{μ}), contradicting our assumption that v, v′ are non-adjacent. Hence B_{μ} is an interface in G. □

We already mentioned that the simplices of attachment in simplicial tree-decomposi-tions into primes are uniquely determined and coincide with the simplices that are minimal relative separators. Indeed, a simplex S ⊂ G that is a minimal relative separator in G is among the simplices of attachment in any simplicial decomposition of G into primes [ 3 ]. The converse, however, is only true for simplicial tree-decompositions:

Proposition 3. Let F be a simplicial tree-decomposition of a graph G into primes, and let S ⊂ G be a simplex. Then S is a simplex of attachment in F if and only if S is a minimal relative separator in G.

Proof. Let F = (B_{λ})_{λ<σ}, and suppose that S = S_{μ}. Then S ⊂ B_{λ} for some λ < μ (S4). Since B_{μ} and B_{λ} are prime, S is attached to B_{λ}\S as well as to B_{μ}\S [ 4, Corollary 1.3 ], so S is a minimal relative separator in G. □

Let us now sum up the uniqueness properties of reduced prime decompositions in a single theorem.

Theorem 4. Let G be a countable graph, B an induced subgraph of G, and S ⊂ G a simplex. Suppose that G has a reduced simplicial tree-decomposition F into primes.

(i) The following statements are equivalent:

(a) B is maximally prime in G and either strongly unattached or an interface;

(b) B is minimally convex in G and either strongly unattached or an interface;

(c) B is a factor in F.

(ii) S is a simplex of attachment in F if and only if S is a minimal relative separator in G.

Proof. Part (ii) of the theorem follows from Proposition 3. In part (i), the implications (c) ⇒ (a) and (c) ⇒ (b) can be read out of Corollary 2 and [ 4, Theorem 1.10 ]. The reverse implications, (a) ⇒ (c) and (b) ⇒ (c), follow from Theorem 1 (i) (if B is a simplex) or from [ 4, Theorem 1.11 ] (if B is not a simplex). □

Corollary 5. If a countable graph has a reduced simplicial tree-decomposition into primes, then its factors and simplices of attachment in any such decomposition are uniquely determined. □

In fact, Corollary 5 is still valid for uncountable graphs, whose indispensable prime factors can be characterized in way similar to—though less attractive than—Theorem 1 and Corollary 2, without reference to any fixed prime decomposition. If G is an arbitrary graph and S ⊂ G a simplex, let us call a family (C_{n})_{n^{∈}ℕ} of components of G\S comprehensive if for every component C of G\S there is some n ^{∈} ℕ such that S [ C] ⊂ S [ C_{n}]. Moreover, let us say that S is the yield of such a family if S = ⋃_{n^{∈}ℕ} S [ C_{n}] and S [ C_{n}] ⊂ S [ C_{n+1} ] for every n.

Theorem 6. Let G be a graph of arbitrary cardinality, S ⊂ G a simplex, and F a simplicial tree-decomposition of G into primes. Then S is an indispensable factor in F if and only if S is not the yield of a comprehensive family of components of G\S.

The proof of Theorem 6 is very similar to that of Theorem 1, and left to the reader. (In fact, the proof is even simpler than that of Theorem 1, in which a comprehensive family of components of G\S first has to be found, using the simpler but also weaker concept of an interface.)

If a ‘comprehensive family’ is defined in a slightly more complicated way, Theorem 6 can even be adapted to simplicial decompositions that are not necessarily tree-decom-positions. Thus for general simplicial decompositions, too, the factors in reduced prime decompositions (defined analogously) are uniquely determined. Details will be given in [ 3 ].

The immediate question arising from these results is whether every graph that has some simplicial (tree-) decomposition into primes also has a reduced such decomposition— in which case prime decompositions could in practice be taken reduced as a matter of course. However, this is not the case: Section 4 contains an example of a graph that has a simplicial tree-decomposition into primes but no reduced prime decomposition.

It is an open problem to determine which graphs have a reduced simplicial tree-decom-position into primes.

3. Proof of Theorem 1

Let G, F and S be given as stated in Theorem 1. To prove assertion (i), let us suppose that S is strongly unattached or an interface in G. Since any interface is unattached, S is unattached and hence a maximal simplex in G. We can therefore apply [ 4, Theorem 3.2 ].

Suppose Λ(S) is infinite. Then [ 4, Theorem 3.2 (iv) ] applies; let Λ and (C_{λ})_{λ^{∈}Λ} be given as stated there. Since

S = ⋃_{λ^{∈}Λ} S|_{λ} = ⋃_{λ^{∈}Λ} S|_{λ^{+}} = ⋃_{λ^{∈}Λ} S [ C_{λ}] ,

S is not strongly unattached in G. But [ 4, Theorem 3.2 ] also implies that Λ(S [ C]) is finite for every component C of G\S, because S is unattached, and hence S [ C] ⫋ S. Thus if C, C′ are components of G\S, then S [ C] ∪ S [ C′] ⊂ S|_{λ} ⊂ S|_{λ^{+}} = S [ C_{λ}] for some λ ^{∈} Λ. Hence S is not an interface either, contrary to our assumption.

Therefore Λ(S) is finite. Since S is unattached, S is a factor in F by [ 4, Theorem 3.2 (i) ].

To prove part (ii) of the theorem, we now assume that S is a factor in F, say S = B_{μ}. Let us suppose that S is neither strongly unattached nor an interface in G, and prove that S is dispensable in F.

Let C denote the set of all components of G\S. Then every B_{λ}, λ ≠ μ, meets exactly one such component C ^{∈} C; for as B_{λ} ⊄ B_{μ} = S by (S3), we have B_{λ}\S ≠ ∅, and if B_{λ} ∩ C ≠ ∅ then B_{λ} ⊂ G [ C → S], because B_{λ} is prime and therefore not separated by any subsimplex of S. We shall use this fact repeatedly later on.

Since the definition of a factor’s dispensability in a given decomposition does not depend on the order of factors in that decomposition, we may assume by [ 4, Theorem 3.1 ] that σ ≤ ω. Then μ is finite, and

C_{0} := { C ^{∈} C | C|_{μ} ≠ ∅ }

is also finite. Since S is by assumption not an interface, this means that there exists a component C_{0} of G\S satisfying

S [ C] ⊂ S [ C_{0} ],  ∀ C ^{∈} C_{0}.  (1)

Let C^{1}, C^{2}, … be a fixed enumeration of C. Define a sequence C_{1}, C_{2}, … of components of G\S by selecting as C_{n} (n = 1, 2, …) any C ^{∈} C satisfying

S [ C_{n−1} ] ∪ S [ C^{k(n)} ] ⊂ S [ C] ,

where k(n) denotes the minimal k for which S [ C^{k}] ⊄ S [ C_{n−1} ] (again using our assumption that S is not an interface). We shall use the notation C_{1} := { C_{1}, C_{2}, … } and C_{2} := C\(C_{0} ∪ C_{1}). Clearly

S [ C_{n}] ⫋ S [ C_{m}]  if 0 ≤ n < m,  (2)

and

∀ C ^{∈} C : ∃ n ^{∈} ℕ : S [ C] ⊂ S [ C_{n}] .  (3)

Since S is by assumption not strongly unattached in G, every vertex of S is contained in S [ C] for some C ^{∈} C, so (3) implies that

S = ⋃_{n=1,2,...} S [ C_{n}] .  (4)

On the other hand, S is unattached in G by [ 4, Theorem 1.10 ], so S ≠ S [ C_{n}] for all n. By (2/4), the sequence C_{1}, C_{2}, … must therefore be infinite. Finally, (1), (2) and the definition of C_{0} imply that

C_{n}|_{μ} = ∅  ∀ n ^{∈} ℕ .  (5)
For each n ^{∈} ℕ set B_{(n)} := B_{λ(C_{n})}, and let
F′ := (B_{λ})_{λ<μ} ⊕ (B_{(n)})_{n=1,2,...} ⊕ (B_{λ})_{{μ<λ<σ \atop B_{λ}≠B_{(n)} ∀ n=1,2,...}}

where ⊕ denotes the concatenation of well-ordered families.

Let us take a closer look at this definition. F′ is a well-ordered family whose members are precisely the members of F other than S = B_{μ}, arranged in a slightly different order. We shall prove that F′ is a simplicial tree-decomposition of G, thus showing that S is dispensable in F. In its first part, F′ coincides with F (up to G|_{μ}). In the middle part of F′, which ‘replaces’ the factor B_{μ}, the simplex S is built up by a sequence of contributions from the factors B_{(n)}; recall that B_{(n)} = B_{λ(C_{n})}, so the simplex of attachment of B_{(n)} in F is precisely S [ C_{n}] (consider the side (C_{n}, S [ C_{n}]) and apply [ 4, Corollary 1.7 (iii) ]). The third part of F′ consists of the remaining factors of F, in their original order.

Our main concern in proving that F′ is indeed a simplicial tree-decomposition, is to verify that every ‘attachment graph’ in F′ is a simplex (S2) and contained in some earlier factor (S4). We shall give a brief outline of the proof at this point, which for the reader familiar with simplicial decompositions may be as illuminating as the subsequent more rigorous proof.

For the first part of F′, (S2) and (S4) are obvious. The first factor of the second part of F′, B_{(1)}, satisfies (S2) and (S4) because, roughly speaking, its relationship to the factors preceding it in F′ is the same as the relationship of S = B_{μ} to the factors preceding B_{μ} in F (by (1/2)), and F satisfies (S2) and (S4) by assumption.

The subsequent factors B_{(n)} in the middle part of F′ will be seen to satisfy (S2) and (S4) because the contribution of each B_{(n)} to the construction of S is the entire segment S [ C_{n}] [ 4, Corollary 1.7 (iii) ], and these segments S [ C_{n}] form a nested sequence by (2).

Checking (S2) and (S4) for the factors B_{λ} in the third part of F′ will depend on the nature of the component C of G\S that contains B_{λ}\S. If C is in C_{0}, the attachment graph of B_{λ} in F′ will be the same as in F, because the transition from F to F′ leaves the subgraphs G [ C → S], C ^{∈} C_{0}, essentially unaffected (again by (1)). If C ^{∈} C_{1}, say C = C_{n}, the attachment of B_{λ} in F′ is again the same as in F. For in both families B_{λ} is preceded by B_{(n)} = B_{λ(C)}, which covers all vertices of G\C that could possibly be contained in B_{λ}, namely those of S [ C]. If C ^{∈} C_{2} finally, then C appears in F′ after the completion of S. By (3), there exists n ^{∈} ℕ with S [ C] ⊂ S [ C_{n}]. For the construction of G [ C → S] in F′, B_{(n)} can therefore assume the role played by B_{μ} in F. Thus again the attachment graph of B_{λ} is the same in F′ as it is in F, and it is contained in the same earlier factor or, in the case of λ = λ(C), in B_{(n)}.

We now give a more detailed proof that F′ is a simplicial tree-decomposition of G. Recall that

B_{(n)} ⊂ G [ C_{n} → S],  ∀ n ^{∈} ℕ ,  (6)

because B_{(n)} ∩C_{n} ≠ ∅ by definition of B_{(n)}, and B_{(n)} is prime. As immediate consequences of (6) and (5/6), respectively, we have

B_{(n)} ∩ B_{(m)} ⊂ S whenever n, m ^{∈} ℕ, n ≠ m ,  (7)

and

B_{(n)}|_{μ} ⊂ S,  ∀ n ^{∈} ℕ .  (8)

Let us first check that F′ satisfies (S1), i.e. that F′ covers S. Let B_{(n)}, n ^{∈} ℕ, be an arbitrary factor from the middle part of F′. Since B_{(n)} ∩ C_{n} ≠ ∅, (5) implies that B_{(n)} ⊄ G|_{μ}. The index of B_{(n)} in F must therefore be greater than μ, say B_{(n)} = B_{τ}, τ > μ. Thus S ⊂ G|_{τ}, so in particular S [ C_{n}] ⊂ G|_{τ}. Therefore S_{τ} = S [ C_{n}] by [ 4, Corollary 1.7 (iii) ]; recall that τ = λ(C_{n}) by definition of B_{(n)}.

Restating this fact without reference to F, we obtain

B_{(n)} ∩ S = S [ C_{n}],  ∀ n ^{∈} ℕ .  (9)

In combination with (4), (9) implies that F′ covers S; thus F′ satisfies (S1).

We now prove that the factors in F′ satisfy (S2) and (S4). This is clear for the factors in (B_{λ})_{λ<μ} (because F satisfies (S2) and (S4)), so let us turn to the middle part of F′. For n ^{∈} ℕ, we shall denote ⋃_{λ<μ} B_{λ} ⊕ ⋃_{i<n} B_{(i)} by G|_{(n)} and B_{(n)} ∩ G|_{(n)} by S_{(n)}.

Let us first look at B_{(1)}. We shall verify (S2) and (S4) for B_{(1)} by showing that S_{(1)} equals S_{μ}. Since S_{(1)} = B_{(1)}|_{μ} ⊂ S by (8), we have S_{(1)} ⊂ S ∩ G|_{μ} = S_{μ}. To see the reverse inclusion, recall first that any factor B_{λ}, λ < μ, satisfies B_{λ} ⊂ G [ C → S] for some C ^{∈} C_{0}, and hence B_{λ} ∩ S ⊂ S [ C] ⊂ S [ C_{0} ] by (1). Therefore

G|_{μ} ∩ S = ⋃_{λ<μ}(B_{λ} ∩ S) ⊂ S [ C_{0} ] ,  (10)

and hence

S_{μ} = G|_{μ} ∩ S
⊂ S [ C_{0} ] ∩ G|_{μ}
⊂ S [ C_{1} ] ∩ G|_{μ}
⊂ B_{(1)} ∩ G|_{μ}
= S_{(1)}

by (2) and (9). Thus S_{(1)} = S_{μ} as claimed, so B_{(1)} satisfies (S2) and (S4).

Let us now check (S2) and (S4) for the remaining factors of the form B_{(n)}. Let n ≥ 2. Then

S_{(n)} = B_{(n)} ∩ G|_{(n)}

= (B_{(n)} ∩ G|_{μ}) ∪ ⋃_{i=1}^{n−1} (B_{(n)} ∩ B_{(i)})

= (B_{(n)} ∩ S ∩ G|_{μ}) ∪ ⋃_{i=1}^{n−1} (B_{(n)} ∩ S ∩ B_{(i)})  (by (8/7))

= (S [ C_{n}] ∩ G|_{μ}) ∪ ⋃_{i=1}^{n−1} (S [ C_{n}] ∩ S [ C_{i}])  (by (9))
= (S [ C_{n}] ∩ G|_{μ}) ∪ S [ C_{n−1} ]  (by (2))
= S [ C_{n−1} ]  (by (10/2))
= B_{(n−1)} ∩ S  (by (9)).

Therefore S_{(n)} is a simplex (S2) contained in an earlier factor of F′ (S4).

It remains to show (S2) and (S4) for the factors in the third part of F′, i.e. for the factors B_{ν} with μ < ν < σ and B_{ν} ≠ B_{(n)} for all n ^{∈} ℕ. Let such B_{ν} be given, and let C be the component of G\S for which B_{ν} ⊂ G [ C → S]. Put

F |_{ν} := (B_{λ})_{λ<ν} ,

and let F′|_{ν} be the corresponding subfamily of F′, i.e.,

F′|_{ν} := (B_{λ})_{λ<μ} ⊕ (B_{(n)})_{n=1,2,...} ⊕ (B_{λ})_{{μ<λ<ν \atop B_{λ}≠B_{(n)} ∀ n=1,2,...}} .

Let us further define

H|′_{ν} := H ∩ ⋃_{B^{∈}F′|_{ν}} B

for subgraphs H of G, and set

S′_{ν} := B_{ν}|′_{ν}.

Thus S′_{ν} is the ‘attachment graph’ of B_{ν} in F′, and we want to show that S′_{ν} is a simplex contained in some B ^{∈} F′|_{ν}.

Note first that every B ⊂ G satisfies

B ^{∈} F |_{ν} ⇔ B ^{∈} F′|_{ν}  if B ∩ C ≠ ∅.  (11)

Indeed, by the construction of F′ we have B ^{∈} F |_{ν} ⇒ B ^{∈} F′|_{ν} unless B = S, but S ∩ C = ∅. And conversely, we have B ^{∈} F′|_{ν} ⇒ B ^{∈} F |_{ν} unless B = B_{(n)} for some n ^{∈} ℕ; but B_{(n)} ∩ C is non-empty only if n is such that C = C_{n}, in which case B = B_{(n)} = B_{λ(C_{n})}, which is in F |_{ν} by B_{ν} ∩ C ≠ ∅, the definition of λ(C_{n}), and the obvious fact that B ≠ B_{ν}.

Moreover,

G [ C → S]|_{ν} = G [ C → S]|′_{ν}.  (12)

To verify (12), notice that any vertex or edge of G [ C → S]|_{ν} or G [ C → S]|′_{ν} that is not contained in S [ C] belongs to some B ^{∈} F |_{ν} (or B ^{∈} F′|_{ν}, respectively) with B ∩C ≠ ∅, and is therefore in G [ C → S]|_{ν} ∩ G [ C → S]|′_{ν} by (11). But S [ C] is a subgraph of G [ C → S]|_{ν} (because S ⊂ G|_{ν}) as well as of G [ C → S]|′_{ν} (by (3/9)), so (12) follows.

Using (12) and the fact that B_{ν} ⊂ G [ C → S], it is easy to determine S′_{ν}:

S′_{ν} = B_{ν} ∩ G|′_{ν}
= B_{ν} ∩ G [ C → S]|′_{ν}
= B_{ν} ∩ G [ C → S]|_{ν}
= B_{ν} ∩ G|_{ν}
= S_{ν} .

Thus S′_{ν} is a simplex because S_{ν} is a simplex, giving (S2). But also (S4) is now obvious: if S′_{ν} ⊂ S, then S′_{ν} ⊂ S [ C] ⊂ B_{(n)} for every sufficiently large n ^{∈} ℕ (3/9). But if S′_{ν} ⊄ S then S′_{ν} ∩ C ≠ ∅, so any B ^{∈} F |_{ν} with S′_{ν} = S_{ν} ⊂ B will also be in F′|_{ν} by (11). Such B exists, because F satisfies (S4).

It remains to check that F′ satisfies (S3). As we have seen, every simplex of attachment in F′ is also a simplex of attachment in F or a subgraph of S = B_{μ}. Moreover, every factor in F′ is also a factor in F, and no factor B_{λ} ^{∈} F, λ ≠ μ, can be contained in B_{μ} or in any simplex of attachment of F, because F satisfies (S3). We may therefore deduce that no factor in F′ can be contained in any simplex of attachment of F′, i.e. F′ satisfies (S3).

This completes the proof of Theorem 1.

4. An Example

We now give an example of a graph which admits a simplicial tree-decomposition into primes, but has no reduced decomposition. Our example is the graph T_{0} introduced in [ 5 ]: its vertices are the finite 0-1 sequences (including the empty sequence), and two vertices (a_{0}, …, a_{μ}) and (b_{0}, …, b_{ν}) are joined by an edge whenever μ < ν and a_{λ} = b_{λ} for λ = 0, …, μ. For every α = (a_{0}, a_{1}, …) ^{∈} { 0, 1 }^{ω}, the subgraph

S_{α} := T_{0}[{(a_{λ})_{λ<μ} | μ < ω}]

of T_{0} spanned by all the finite initial segments of α is a simplex, and it is easily seen that the graphs S_{α}, α ^{∈} { 0, 1 }^{ω}, are precisely the maximally prime subgraphs of T_{0}. Moreover, it is not difficult to arrange them into simplicial tree-decompositions of T_{0}. In fact, if F = (S_{α_{λ}})_{λ<σ} is any maximal (with respect to extension) well-ordered family of S_{α}’s satisfying S_{α_{μ}}\ ⋃_{λ<μ} S_{α_{λ}} ≠ ∅ for all μ < σ, then F is a simplicial tree-decomposition of T_{0} into primes.

However, T_{0} has no reduced prime decomposition. For any factor in such a decomposition must be maximally prime in T_{0} and therefore of the form S_{α}, with α = (a_{λ})_{λ<ω} say. Then the graphs S_{α} [ C] = T_{0} [ C → S_{α}] ∩ S_{α} (for components C of G\S_{α}) are precisely the nested simplices S_{α} [ { a_{λ} | λ < μ }], μ < ω. Therefore S_{α} is neither strongly unattached nor an interface, contrary to Theorem 1.

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 II—the existence 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