A compactness theorem for complete separators (Q1173791)

A subset \(S\) of the vertex set \(V\) of a graph \(G\) is a complete separator of \(G\) if \(S\) induces a complete subgraph of \(G\) and removal of \(S\) increases the number of components of \(G\). The following theorem is proved: Let \(G\) be an infinite graph without a complete separator and \(G'\) be a finite subgraph of \(G\). Then \(G\) has a finite induced subgraph \(H'\supset G'\) which has no complete separator. The proof technique involves a compactness argument using Tychonoff's theorem. Induced subgraphs of \(G\) are represented by points in a compact topological space. Sets of complete separators in every finite induced subgraph of \(G\), containing \(G'\), correspond to closed sets with non- empty finite intersections.