Graph minors and treewidth

A graph H is a minor of G if one can obtain H by deleting vertices, deleting edges, and contracting edges. Equivalently, assign to each vertex of H a disjoint nonempty connected branch set in G, with an edge between branch sets whenever H requires one. Contracting each branch set then realizes H after deleting extras. Unlike a subgraph, a minor can shorten long connected routes. A cycle of length four has a triangle minor even though it contains no triangle subgraph.

A class is minor-closed if every minor of a graph in the class remains inside it. Planarity is an example: deletion and contraction preserve a planar drawing after suitable local adjustment. Neither a numerical density nor a fixed vertex labeling is the defining object. A minor theorem addresses an entire pattern after permitted contractions, whereas a subgraph extremal theorem addresses literal vertex-edge configurations. Switching these meanings can turn a true bound into a false one.

A tree decomposition consists of a tree T and a vertex bag B_t at each tree node. Every graph vertex must appear in some bag, every graph edge must have both endpoints together in some bag, and the bags containing any fixed graph vertex must induce a connected subtree of T. This last running-intersection condition prevents incompatible copies of a vertex from appearing in separated pieces. Merely covering each edge with a small bag is not enough.

The width is the largest bag size minus one, and treewidth is the minimum width over all decompositions. A nontrivial tree has treewidth one; a cycle has treewidth two. Every graph with treewidth at most k has a vertex of degree at most k, and the property persists in subgraphs. Thus it is k-degenerate and has at most kn minus k(k+1)/2 edges when n is at least k+1. The converse fails: low edge count does not force a small-width decomposition.

The grid-minor theorem states that for each positive integer r there is an integer f(r) such that every graph of treewidth at least f(r) contains the r-by-r grid as a minor. This qualitative theorem is stated here, not proved, and no sharp numerical bound for f is asserted. Large square grids have unbounded treewidth despite being planar with maximum degree four. Consequently sparsity and planarity alone do not make treewidth uniformly bounded.

For a fixed finite graph H, the class of H-minor-free graphs has bounded treewidth exactly when H is planar. The forward obstruction for nonplanar H is immediate from grids: all grids are planar and avoid H, yet their widths grow. The converse combines the grid theorem with the fact that every fixed planar graph is a minor of a sufficiently large grid. This is a uniform statement about a graph class, not a claim that excluding a minor makes every individual graph literally a tree.