####

#### 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.