Highly connected sets and the excluded grid theorem

We present a short proof of the excluded grid theorem of Robertson and Seymour, the fact that a graph has no large grid minor if and only if it has small tree-width. We further propose a very simple obstruction to small tree-width inspired by that proof, showing that a graph has small tree-width if and only if it contains no large highly connected set of vertices.

Download (DVI)

A better exposition with figures is available in the chapter on graph minors in Graph Theory, 2nd ed'n.