A compactness theorem for complete separators

Reinhard Diestel, Cambridge

Amongst K. Wagner’s early graph-theoretical works, the one with indisputably the greatest impact on the further development of the discipline was his paper Über eine Eigenschaft der ebenen Komplexe [ 3 ]. This paper broke new ground in several respects, inspiring such profound work as − the theory of simplicial decompositions of graphs, as initiated by R. Halin in the 1960s

(see [ 1 ]); − tree-decompositions and well-quasi-ordering theory for finite graphs, as recently

started by N. Robertson and P. D. Seymour with most impressive results; − excluded minor theorems, as pursued later by K. Wagner himself as well as many other

authors (see [ 1 ] for an overview).

The following problem, which arises in the context of infinite excluded minor theorems [ 2 ], concerns separating complete subgraphs (or, complete separators):

Given an infinite graph G which has no complete separator, and given a finite subgraph G′ ⊂ G, is there a finite induced subgraph H′ of G without a complete separator, such that G′ ⊂ H′?

Apart from their use in excluded minor theorems, induced subgraphs without complete separators play a key role in the theory of simplicial decompositions of graphs [ 1 ], which gives the above problem some weight of its own.

If we bound the order of the complete separators under consideration by some fixed natural number k, then, as Kříž and Thomas [ 2 ] observed, the problem has a straightforward positive solution: if a graph G has no complete separator of order < k, then any finite G′ ⊂ G can be extended to a finite induced subgraph H′ of G which has no complete separator of order < k either.

The purpose of this note is to settle the general case of the problem:

Theorem. Let G be a graph which has no complete separator, and let G′ ⊂ G be finite. Then G has a finite induced subgraph H′ ⊃ G′ which has no complete separator.

Proof. Let H denote the set of all finite induced subgraphs of G which contain G′. Suppose the theorem fails, i.e. that every graph in H has a complete separator. Our aim is to show that now G, too, must have a complete separator, contrary to the assumptions of the theorem.

Essentially, this extension from the finite parts of G to G itself will be achieved by a well-known compactness argument: we shall represent the induced subgraphs of G as points in a compact topological space, so that the sets of complete separators which we are assuming to exist in every graph of H correspond to closed sets with non-empty finite intersections; then, by compactness, there will be a point in the overall intersection of these sets, and this point will correspond to a complete separator of G.

However, our assumed collection of complete separators for the graphs in H is not, in its raw form, fit for translation into a suitable system of closed sets: the problem is that vertices separated by a complete subgraph in one H ^{∈} H may not be separated by a complete subgraph in another graph of H, even if this is a subgraph of H. Before we can apply the compactness argument outlined above, we have to remove this arbitrariness and find two fixed vertices u and v which can be separated by a complete subgraph in every H ^{∈} H. This will be done in two stages. First we show that every H ^{∈} H may be assumed to have a complete subgraph which separates two vertices lying in G′. In the second step the choice of these two vertices is narrowed down to one pair.

Let us call two vertices u, v of a graph H close in H if they are not separated by any complete subgraph of H. Moreover, let us say that a subgraph H′ ⊂ H is convex in H if every induced path P ⊂ H with endvertices in H′ lies entirely inside H′. The convex hull in H of a set of vertices of H is the intersection of all convex subgraphs of H containing these vertices; this intersection is clearly again convex in H.

The following lemma is an easy consequence of these definitions (and one of the basic facts of simplicial decomposition theory):

Lemma. [ 1 ] The convex hull of any set of pairwise close vertices in a graph has no complete separator.

Now, if there exists a graph H ^{∈} H in which the vertices of G′ are pairwise close, then by the lemma the convex hull of V (G′) in H may serve as the graph H′ whose existence is claimed in the theorem; note that since H is induced in G by assumption and H′ is induced in H by its convexity, H′ is induced in G as required. We may therefore assume from now on that for every H ^{∈} H there exist vertices u, v ^{∈} G′ which are separated in H by a complete subgraph.

Let us now show that there exists a choice of u and v which works uniformly for all H ^{∈} H. Suppose the contrary, i.e. that for each pair of vertices u, v ^{∈} G′ there exists a graph H(u, v) ^{∈} H in which u and v are close. Let H be the subgraph induced in G by the union of all the graphs H(u, v). Then H is finite and contains G′, so H ^{∈} H. By assumption, there exist vertices u, v ^{∈} G′ which are separated in H by a complete subgraph S. But then S ∩ H(u, v) is a complete subgraph of H(u, v) separating u and v in H(u, v), contrary to the choice of H(u, v).

We have thus established the existence of two vertices u, v ^{∈} G′ such that every H ^{∈} H has a complete subgraph S_{H} separating u and v in H. Now consider the topological space

X = { 0, 1 }^{V (G)\{ u,v }} ,

where { 0, 1 } carries the discrete topology and X the product topology. Since { 0, 1 } is trivially compact, X is compact by Tychonoff’s theorem. Identifying x ^{∈} X with the set x^{−1}(1) ⊂ V (G)\{ u, v } as usual, let us set

A_{H} := { x ^{∈} X | G [ x ∩ V (H) ] is a complete separator of u and v in H }

for H ^{∈} H. Every A_{H} is closed (as well as open) in X, and A_{H} ≠ ∅ because V (S_{H}) ^{∈} A_{H}. Moreover, since S_{H} ∩ H′ separates u and v in any H′ ⊂ H, we have

A_{H_{1}} ∩ … ∩ A_{H_{n}} ⊃ A_{G [ H_{1}∪...∪H_{n} ]} ≠ ∅

for every finite subset { H_{1}, …, H_{n} } of H.

By the compactness of X, this implies that ⋂_{H^{∈}H} A_{H} ≠ ∅. Pick x ^{∈} ⋂_{H^{∈}H} A_{H}, and let S := G [ x]. As every two vertices of S are contained in some common H ^{∈} H and are thus adjacent (since x ^{∈} A_{H}), S is a complete subgraph of G. Furthermore, every u–v path P in G is finite and therefore contained in some H ^{∈} H, giving P ∩ (S ∩ H) ≠ ∅ (again since x ^{∈} A_{H}). Hence, S separates u and v in G, so G has a complete separator as claimed. □

References

[ 1 ] R. Diestel, Graph decompositions, Oxford University Press, in preparation. [ 2 ] I.Kříž and R. Thomas, Clique-sums, tree-decompositions and compactness, Discrete Math. (to ap-

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

Reinhard Diestel, St. John’s College, University of Cambridge, Cambridge CB2 1TP, England.