Highly connected sets and the excluded grid theorem (Q1306423)

In their work on graph minors, Robertson and Seymour prove that the class of graphs without a fixed minor \(X\) has bounded tree-width if and only if \(X\) is planar. This is quickly seen to be equivalent to the result that for every \(r\) there is a \(k\) such that every graph of tree-width at least \(k\) has an \(r \times r\) grid minor. The authors give a new short proof of this excluded grid theorem. The authors also propose a simple obstruction to small tree-width. A set \(X\) of at least \(k\) vertices is \(k\)-connected in a graph \(G\) if every pair of subsets of \(X\) of size \(j \leq k\) are joined by \(j\) disjoint paths. The authors show that a graph has small tree-width if and only if it has no large highly connected sets of vertices. This work is a nice contribution to the growing literature on graph minors.