40.04.10 · combinatorics / graph-theory-core

Graph Minors and the Robertson-Seymour Theorem

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 12 in full (§12.4 brambles and tree-width duality, §12.5 the excluded-grid theorem, §12.6 the structure theorem for graphs with an excluded minor, the graph-minor theorem and its algorithmic consequences); Lovász 2006 *Graph Minor Theory* (Bull. AMS 43) for the survey; the original Robertson-Seymour *Graph Minors* series I-XX (1983-2004), in particular XIII (the disjoint-paths algorithm), XVI (the structure theorem), XX (Wagner's conjecture); Kruskal 1960 and Nash-Williams 1963 for well-quasi-ordering

Intuition Beginner

There is a way to simplify a graph that is gentler than just deleting parts of it. You may delete a dot, delete a line, or — the new move — shrink a line until its two dots merge into one. A graph you can reach from another by these three moves is called a minor of it. Shrinking a line keeps the connections alive: anything that was reachable through that line is still reachable through the merged dot. So a minor is a smaller graph that the bigger one secretly contains, with whole connected clumps allowed to collapse to single dots.

This matters because many natural properties of graphs are inherited by minors. If a graph can be drawn flat on paper with no crossings, then so can every minor of it; shrinking and deleting never force a new crossing. A family of graphs closed under taking minors is called minor-closed, and "can be drawn flat" is the first example you already met: the planar graphs form such a family.

Now the surprise. For planarity there are exactly two forbidden patterns: a graph is flat-drawable unless it hides one of two specific small graphs as a minor. The deep theorem of this subject says this is no accident. Every minor-closed family whatsoever — however exotic — is described by a finite list of forbidden patterns. There may be billions of them, but always finitely many. That single fact is the Robertson-Seymour theorem, one of the longest proofs in mathematics.

Visual Beginner

Picture the move that makes minors special: contracting a line. Take a small graph shaped like a square with one diagonal, and shrink the diagonal so its two end-dots slide together into a single dot. The lines that touched either end-dot now all touch the merged dot, and any doubled line is kept just once.

The table beside the drawing lists the three moves that build a minor. Only the third is new; the first two you already know.

move	what it does
delete a dot	remove a vertex and every line touching it
delete a line	remove an edge, keeping its two dots
contract a line	merge a line's two dots into one, keeping their other connections

Apply any sequence of these three moves and whatever graph you end up with is a minor of the one you started from. The square-with-diagonal has a triangle as a minor, because contracting the diagonal merges two corners and leaves three dots in a triangle.

Worked example Beginner

Show by hand that a five-dot path has a four-dot path as a minor, using only the allowed moves. Label the path's dots $1, 2, 3, 4, 5$ joined in a line: $1 - 2 - 3 - 4 - 5$ . We want to reach the four-dot path $a - b - c - d$ .

Step 1. Decide which move to use. The five-dot path has five dots; the target has four. We need to lose exactly one dot while keeping everything in a single line, so contraction is the natural choice — deletion would break the line into pieces.

Step 2. Contract the line between dots $1$ and $2$ . They merge into one dot; call it $12$ . The merged dot inherits dot $1$ 's connections (none beyond $2$ ) and dot $2$ 's connection to $3$ .

Step 3. Read off the new graph. The dots are now $12, 3, 4, 5$ joined as $12 - 3 - 4 - 5$ . That is a path on four dots.

Step 4. Match it to the target. Rename $12 \to a$ , $3 \to b$ , $4 \to c$ , $5 \to d$ . The result is exactly the four-dot path $a - b - c - d$ .

What this tells us: a single contraction turned the longer path into the shorter one without ever cutting the line apart. Contraction is the move that lets a graph "contain" a smaller, simpler shape even when no piece of it sits there as an exact copy. That is why minors capture more than subgraphs do.

Check your understanding Beginner

Formal definition Intermediate+

Recall from 40.04.01 that $H$ is a minor of $G$ , written $H ≼ G$ , if $H$ is obtained from a subgraph of $G$ by contracting edges; equivalently there is a family of disjoint connected branch sets ${B_{x}}_{x \in V (H)}$ in $G$ , one per vertex of $H$ , with an edge of $G$ between $B_{x}$ and $B_{y}$ whenever $x \sim y$ in $H$ . The map sending $x$ to $B_{x}$ is a model (or minor model) of $H$ in $G$ . The relation $H ≼ G$ is a topological minor, written $H ≼_{top} G$ , when $G$ contains a subdivision of $H$ ; every topological minor is a minor, and for graphs of maximum degree at most three the two relations coincide ^{[Diestel 2017 §12.1]}.

A quasi-order is a reflexive transitive relation $\leq$ on a set $Q$ . A sequence $q_{1}, q_{2}, \dots$ in $Q$ is good if $q_{i} \leq q_{j}$ for some $i < j$ , and bad otherwise. The quasi-order is a well-quasi-ordering (wqo) if every infinite sequence is good. Equivalently, $\leq$ is a wqo iff it has no infinite strictly descending chain and no infinite antichain (set of pairwise incomparable elements), iff every set has finitely many minimal elements up to equivalence ^{[Diestel 2017 §12.1]}. The minor relation $≼$ is a quasi-order on the class of (isomorphism types of) finite graphs.

A tree-decomposition of $G$ is a pair $(T, {V_{t}}_{t \in V (T)})$ with $T$ a tree and each bag $V_{t} \subseteq V (G)$ satisfying: every vertex of $G$ lies in some bag; every edge of $G$ has both ends in some common bag; and for each vertex $v$ the set ${t : v \in V_{t}}$ induces a connected subtree of $T$ ^{[Diestel 2017 §12.3]}. The width of the decomposition is $max_{t} ∣ V_{t} ∣ - 1$ , and the tree-width $tw (G)$ is the minimum width over all tree-decompositions of $G$ . Trees have tree-width $1$ ; the $k \times k$ grid has tree-width exactly $k$ . A bramble is a set $B$ of connected subgraphs of $G$ , pairwise touching (sharing a vertex or joined by an edge); its order is the least size of a vertex set meeting every member, and the maximum bramble order over all brambles is the bramble number $bn (G)$ .

Counterexamples to common slips

A minor need not be a subgraph. The triangle $K_{3}$ is a minor of the path on four vertices' suspension but the path itself contains no triangle subgraph; contraction creates adjacencies that deletion alone cannot.
Topological minor is strictly stronger than minor. $K_{5}$ is a minor of the Petersen graph but not a topological minor of it, since the Petersen graph is $3$ -regular and a $K_{5}$ subdivision needs four branch vertices of degree four. The two notions agree only when the model graph has maximum degree at most three.
Tree-width is not the same as having a small separator. A single small separator does not bound tree-width; tree-width measures a recursive family of separators arranged on a tree. The complete graph $K_{n}$ has tree-width $n - 1$ despite every vertex being a cut of nothing.
Well-quasi-ordering is more than having no infinite descending chain. The subgraph relation has no infinite descending chains on finite graphs (the cycles $C_{3}, C_{4}, C_{5}, \dots$ form an infinite antichain), yet it is not a wqo. Forbidding both descending chains and antichains is essential.

Key theorem with proof Intermediate+

Theorem (Kruskal's tree theorem). The class of finite rooted trees is well-quasi-ordered under the topological-minor (embeddability) relation: for every infinite sequence $T_{1}, T_{2}, \dots$ of finite trees there exist $i < j$ with $T_{i} ≼_{top} T_{j}$ . (Kruskal ^{[Kruskal 1960]}; the proof here is Nash-Williams' ^{[Nash-Williams 1963]}.)

Proof. Suppose for contradiction the relation is not a wqo, so a bad sequence exists. Construct a minimal bad sequence $T_{1}, T_{2}, \dots$ as follows: having chosen $T_{1}, \dots, T_{n - 1}$ so that they begin some bad sequence, let $T_{n}$ be a tree of fewest vertices such that $T_{1}, \dots, T_{n}$ still begins some bad sequence. This recursion produces an infinite bad sequence in which each term is as small as possible given its predecessors.

Each $T_{n}$ has at least one vertex; let $r_{n}$ be its root and let $A_{n}$ be the set of component subtrees hanging below the root — the trees rooted at the children of $r_{n}$ , each smaller than $T_{n}$ . Form the union $A = ⋃_{n} A_{n}$ of all these component subtrees. The set $A$ is well-quasi-ordered under $≼_{top}$ : any bad sequence drawn from $A$ would, by replacing its first term's containing tree $T_{m}$ with that strictly smaller component subtree, yield a bad sequence contradicting the minimal choice of $T_{m}$ — because the component subtree has fewer vertices than $T_{m}$ , and the tail of the minimal sequence past $T_{m}$ can be appended to extend it badly.

Now apply the fact that finite sequences over a wqo are themselves wqo under the subsequence-domination order (Higman's lemma). Each $T_{n}$ is encoded by its root together with the finite multiset $A_{n}$ of component subtrees from the wqo $A$ . By Higman's lemma the sequence $A_{1}, A_{2}, \dots$ of finite multisets is good: there are $i < j$ with $A_{i}$ dominated by $A_{j}$ , meaning an injection $A_{i} \to A_{j}$ matching each component subtree to one it embeds into. Rooting all trees at their roots, these embeddings assemble into a topological embedding $T_{i} ≼_{top} T_{j}$ , attaching the matched subtrees below the common root. This contradicts badness. $□$

Bridge. Kruskal's theorem builds toward the Robertson-Seymour theorem and appears again in every well-quasi-ordering argument of structural graph theory, because the minimal-bad-sequence engine that proves it is exactly the engine that, run on graphs of bounded tree-width and then on all graphs, proves the minor relation is a wqo. The foundational reason trees come first is that a tree-decomposition reduces a graph to a tree of small bags, so once trees are well-quasi-ordered the bounded-width case follows by quasi-ordering the bags along the decomposition tree; this is exactly the principle that controlling the tree skeleton controls the whole graph. Higman's lemma is dual to the tree case — finite sequences and finite trees over a wqo stay wqo — and putting these together gives the inductive ladder from sequences to trees to tree-like graphs to arbitrary graphs. The central insight is that well-quasi-ordering is a closure property: it survives the constructions (finite multisets, rooted trees, bounded-width tree-decompositions) out of which graphs are built, and the bridge is tree-width, the parameter that measures how tree-like a graph is and so how directly Kruskal's argument transfers to it.

Exercises Intermediate+

Exercise 3 (medium, short-answer).

Deduce from the Robertson-Seymour theorem that every minor-closed class of graphs is characterised by a finite set of forbidden minors. Identify this set for the class of planar graphs.

Hint

The minor-minimal graphs outside a minor-closed class form an antichain.

Answer

Let $C$ be minor-closed and let $F$ be its set of minor-minimal forbidden graphs — those not in $C$ but with every proper minor in $C$ . By minor-closure, $G \in C$ iff $G$ has no member of $F$ as a minor. The set $F$ is an antichain under $≼$ : any two of its members are incomparable, since a minor relation between them would violate minimality. By the Robertson-Seymour theorem $≼$ is a wqo, and a wqo has no infinite antichain, so $F$ is finite. For planar graphs $F = {K_{5}, K_{3, 3}}$ , which is Wagner's theorem 40.04.05. Rubric: full credit for the antichain argument, the appeal to wqo, and the planar obstruction set.

Exercise 4 (medium, short-answer).

Prove that tree-width is minor-monotone: if $H ≼ G$ then $tw (H) \leq tw (G)$ .

Hint

Show separately that deleting a vertex, deleting an edge, and contracting an edge do not increase tree-width, working from a fixed optimal decomposition of $G$ .

Answer

Fix an optimal tree-decomposition $(T, {V_{t}})$ of $G$ of width $tw (G)$ . Deleting a vertex $v$ from $G$ : remove $v$ from every bag; all three decomposition axioms persist and no bag grew, so the width does not increase. Deleting an edge: the same decomposition still satisfies the axioms (fewer edges to cover), with unchanged bags. Contracting an edge $e = uv$ into a new vertex $w$ : in each bag replace $u$ or $v$ (whichever appears) by $w$ . The subtrees ${t : u \in V_{t}}$ and ${t : v \in V_{t}}$ are connected and, because $u \sim v$ , share a bag, so their union is connected, giving a connected subtree for $w$ ; edge-coverage and vertex-coverage carry over, and each bag's size did not increase. Hence each minor operation leaves the width no larger, so any minor $H$ of $G$ has $tw (H) \leq tw (G)$ . Rubric: full credit for handling all three operations and the connected-subtree merge under contraction.

Exercise 5 (medium, short-answer).

Show that the class of graphs of tree-width at most $k$ is minor-closed, and explain why the Robertson-Seymour theorem then guarantees it has a finite obstruction set.

Hint

Combine the previous exercise with the antichain argument of Exercise 3.

Answer

If $tw (G) \leq k$ and $H ≼ G$ , then $tw (H) \leq tw (G) \leq k$ by minor-monotonicity (Exercise 4), so the class $T_{k} = {G : tw (G) \leq k}$ is minor-closed. By the Robertson-Seymour theorem $≼$ is a wqo, so the minor-minimal graphs outside $T_{k}$ form a finite antichain (Exercise 3): there is a finite set $F_{k}$ with $tw (G) \leq k$ iff $G$ excludes every member of $F_{k}$ as a minor. (For $k = 1$ the single obstruction is $K_{3}$ ; for $k = 2$ it is $K_{4}$ ; for $k = 3$ there are four obstructions including $K_{5}$ .) Rubric: full credit for minor-closure via Exercise 4 and the finite-obstruction deduction.

Exercise 6 (medium, numeric).

Robertson and Seymour's minor-testing algorithm decides, for each fixed graph $H$ , whether $H ≼ G$ in time $O (n^{3})$ where $n = ∣ V (G) ∣$ . Using this, what is the polynomial running time of an algorithm that tests membership in a fixed minor-closed class with obstruction set of size $m$ ?

Hint

Run the cubic minor test once per obstruction and report membership iff all tests fail.

Answer

$O (n^{3})$ . Membership in the class holds iff none of the $m$ obstructions is a minor of $G$ . Running the $O (n^{3})$ test once for each of the $m$ fixed obstructions costs $O (m \cdot n^{3})$ ; since $m$ is a constant (the class is fixed), this is $O (n^{3})$ . The decidability is non-constructive in $H$ — the algorithm exists but the obstruction set is not produced by the theorem — yet the running time is cubic. Rubric: full credit for $O (n^{3})$ with the constant- $m$ justification.

Exercise 7 (hard, short-answer).

Prove Higman's lemma in the special case needed for Kruskal's theorem: if $(Q, \leq)$ is a well-quasi-ordering, then the set $Q^{*}$ of finite sequences over $Q$ , ordered by $a \leq^{*} b$ iff $a$ embeds into $b$ as a subsequence with $a_{i} \leq b_{σ (i)}$ for an increasing $σ$ , is also a wqo.

Hint

Use a minimal-bad-sequence argument: take a bad sequence of sequences with each chosen of least length given its predecessors, then look at the first entries.

Answer

Suppose $\leq^{*}$ is not a wqo and build a minimal bad sequence $s_{1}, s_{2}, \dots$ in $Q^{*}$ : each $s_{n}$ has least possible length so that $s_{1}, \dots, s_{n}$ extends to a bad sequence. No $s_{n}$ is empty (an empty sequence embeds into everything, so it cannot sit in a bad sequence). Write $s_{n} = (a_{n}) ⌢ t_{n}$ , splitting off the first entry $a_{n} \in Q$ and the tail $t_{n} \in Q^{*}$ . Since $(Q, \leq)$ is a wqo, the sequence $a_{1}, a_{2}, \dots$ has an infinite ascending-or-equal subsequence indexed by $n_{1} < n_{2} < \dots$ with $a_{n_{1}} \leq a_{n_{2}} \leq \dots$ (a wqo's infinite sequences contain an infinite chain). Consider the sequence $s_{1}, \dots, s_{n_{1} - 1}, t_{n_{1}}, t_{n_{2}}, t_{n_{3}}, \dots$ , which replaces the tail from position $n_{1}$ onward by the strictly shorter tails. By minimality of $s_{n_{1}}$ this sequence is good, so two of its terms are comparable. They cannot both lie in the unchanged prefix (that prefix is bad), and a prefix term cannot embed into a tail $t_{n_{j}}$ (else it would embed into $s_{n_{j}} \supseteq t_{n_{j}}$ , contradicting badness of the original). So some $t_{n_{i}} \leq^{*} t_{n_{j}}$ with $i < j$ ; prepending $a_{n_{i}} \leq a_{n_{j}}$ gives $s_{n_{i}} \leq^{*} s_{n_{j}}$ , contradicting badness of the original sequence. Hence $\leq^{*}$ is a wqo. Rubric: full credit for the minimal-bad-sequence setup, the first-entry chain extraction, and the prefix/tail comparison case analysis.

Exercise 8 (hard, short-answer).

Assuming the excluded-grid theorem (a minor-closed class has bounded tree-width iff it excludes some grid as a minor), prove that for every planar graph $H$ there is a constant $w$ such that every graph excluding $H$ as a minor has tree-width at most $w$ .

Hint

A planar graph is itself a minor of a large enough grid.

Answer

Every planar graph $H$ is a minor of some grid: a plane embedding of $H$ can be placed on a sufficiently fine grid, with each vertex and each edge-arc realised inside grid cells, so contracting the grid pieces yields $H$ . Fix $r$ with $H ≼ G_{r \times r}$ . Now let $C_{H}$ be the class of graphs excluding $H$ as a minor; it is minor-closed. If some graph $G \in C_{H}$ had the $r \times r$ grid as a minor, then $H ≼ G_{r \times r} ≼ G$ by transitivity, contradicting $G \in C_{H}$ . So $C_{H}$ excludes the $r \times r$ grid, and by the excluded-grid theorem $C_{H}$ has bounded tree-width: there is a $w = w (r)$ with $tw (G) \leq w$ for all $G \in C_{H}$ . Rubric: full credit for embedding $H$ in a grid, the transitivity step, and the appeal to the excluded-grid theorem.

Advanced results Master

Theorem (Robertson-Seymour; the graph-minor theorem). The class of finite graphs is well-quasi-ordered by the minor relation $≼$ : every infinite sequence $G_{1}, G_{2}, \dots$ contains indices $i < j$ with $G_{i} ≼ G_{j}$ . (Robertson-Seymour ^{[Robertson Seymour 2004]}; Diestel ^{[Diestel 2017 §12.6]}.) Equivalently, the finite graphs contain no infinite antichain under $≼$ . The proof spans the twenty-paper Graph Minors series and runs by transfinite induction on the structure of an excluded minor: one shows that for each fixed $H$ the $H$ -minor-free graphs admit a tree-decomposition into pieces almost embeddable in a fixed surface, then well-quasi-orders those pieces by combining Kruskal-type arguments over the tree-decomposition with the wqo of graphs embeddable in a fixed surface.

Corollary (finite obstruction sets and cubic membership). Every minor-closed class $C$ has a finite set $F$ of forbidden minors with $G \in C ⟺$ no member of $F$ is a minor of $G$ ; and for each fixed $H$ the test $H ≼ G$ runs in time $O (n^{3})$ , so membership in $C$ is decidable in cubic time. The obstruction set $F$ is the antichain of minor-minimal graphs outside $C$ , finite because $≼$ is a wqo. The cubic minor test is the disjoint-paths algorithm of Graph Minors XIII; the decidability is non-uniform and non-constructive, since the theorem proves $F$ finite without exhibiting it, so the algorithm is known to exist for each $C$ without an effective procedure producing it from a description of $C$ ^{[Robertson Seymour 2004]}.

Theorem (tree-width duality; the bramble theorem). For every graph $G$ , $tw (G) = bn (G) - 1$ : the minimum width of a tree-decomposition is one less than the maximum order of a bramble. (Diestel ^{[Diestel 2017 §12.4]}.) A bramble of order $> k$ is an obstruction to tree-width $< k$ , and the duality says these obstructions are exact: if no bramble has order exceeding $k$ , a tree-decomposition of width $< k$ exists. This is a min-max theorem of the Menger family — a width parameter equals the order of the best dual obstruction — and it is equivalent to the characterisation of tree-width by the monotone cops-and-robber game, where $tw (G) + 1$ cops suffice to catch a robber on $G$ .

Theorem (excluded-grid / grid-minor theorem). There is a function $f$ such that every graph of tree-width at least $f (k)$ contains the $k \times k$ grid as a minor; consequently a minor-closed class has bounded tree-width iff it excludes some grid. (Robertson-Seymour ^{[Robertson Seymour 1986]}; Diestel ^{[Diestel 2017 §12.5]}.) The grid is the canonical large-tree-width obstruction: tree-width is large precisely when a large grid minor is present. Robertson and Seymour's original $f$ was enormous (tower-type in $k$ ); later work brought it down to a polynomial $f (k) = O (k^{9} polylog k)$ , showing the dependence is genuinely polynomial.

Theorem (structure theorem for excluded minors). For every graph $H$ there are integers $h, g, a, b$ such that every $H$ -minor-free graph has a tree-decomposition in which every bag (torso) is, after deleting at most $a$ apex vertices, the clique-sum of a graph embeddable in a surface of genus at most $g$ together with at most $b$ bounded-width vortices glued into its faces. (Robertson-Seymour ^{[Robertson Seymour 2003]}; Diestel ^{[Diestel 2017 §12.6]}.) The four ingredients — bounded-genus surface embedding, a bounded number of vortices of bounded path-width attached along face boundaries, a bounded number of apex vertices joined arbitrarily, and clique-sums assembling the pieces along a tree — are each necessary: deleting any one allows graphs that exclude $H$ yet escape the remaining description. Wagner's clique-sum decomposition of $K_{5}$ -minor-free graphs 40.04.05 is the genus-zero, no-vortex, no-apex prototype.

Theorem (Hadwiger's conjecture; partial). Hadwiger's conjecture asserts that every graph with no $K_{t}$ minor is $(t - 1)$ -colourable. The cases $t = 1, 2, 3$ are elementary; $t = 4$ is equivalent to the statement that $K_{4}$ -minor-free graphs are series-parallel and $3$ -colourable; $t = 5$ and $t = 6$ are theorems, each reducing to the four-colour theorem. (Hadwiger ^{[Hadwiger 1943]}.) The case $t = 5$ is Wagner's reformulation: a graph with no $K_{5}$ minor decomposes by clique-sums into planar pieces and copies of the Wagner graph $V_{8}$ , all $4$ -colourable, and clique-sums preserve $4$ -colourability, so the four-colour theorem 40.04.08 gives $4$ -colourability. The case $t = 6$ was proved by Robertson, Seymour, and Thomas in 1993, again by reduction to the four-colour theorem via a structural analysis of minimal counterexamples. For $t \geq 7$ the conjecture is open, a vast strengthening of the four-colour theorem and one of the central open problems of graph theory.

Synthesis. These results are one phenomenon — that minor-closure is a finiteness constraint — seen at four depths, and putting these together the chapter becomes the study of how a global containment order collapses to finite local data. The foundational reason the graph-minor theorem, tree-width duality, the grid theorem, and the structure theorem cohere is that each says a minor-closed class is governed by a single tree-like skeleton: the wqo gives a finite obstruction set, the duality identifies tree-width with its exact dual bramble, the grid theorem names the one unavoidable obstruction to small tree-width, and the structure theorem describes what bounded-obstruction graphs actually look like. The central insight is that excluding a minor forces tree-like structure, and this is exactly the principle behind both the cubic membership algorithm and the dynamic programming that bounded tree-width enables. Tree-width duality is dual to the grid theorem in the literal min-max sense — a bramble certifies large width, a grid realises it — and the bridge onward is from planarity to all of structural graph theory: Wagner's theorem 40.04.05 is the genus-zero instance of the structure theorem and the $t = 5$ case of Hadwiger's conjecture, so the two forbidden graphs $K_{5}, K_{3, 3}$ that organise planarity generalise into the surface-plus-vortices-plus-apex description that organises every excluded minor. The graph-minor theorem generalises Kruskal's tree theorem from trees to all graphs by replacing the rooted-subtree recursion with the tree-decomposition recursion, and the same minimal-bad-sequence argument drives both.

Full proof set Master

Proposition 1 (the minor relation is a quasi-order; topological minors are minors). The relation $≼$ is reflexive and transitive on finite graphs, and $H ≼_{top} G$ implies $H ≼ G$ .

Proof. Reflexivity: $G$ is its own minor via the singleton model $B_{v} = {v}$ . Transitivity: given models of $H$ in $G$ and of $G$ in $K$ , compose them by taking, for each vertex $x$ of $H$ , the union of the $G$ -model branch sets indexed by the vertices of $B_{x}$ ; each such union is connected (it is a union of connected branch sets joined along the edges realising the connected subgraph $B_{x} \subseteq G$ ), the unions are disjoint, and an edge of $H$ between $x, y$ lifts through both models to an edge of $K$ , so the composite is a model of $H$ in $K$ . For the last claim, a subdivision of $H$ in $G$ yields a model of $H$ by taking each branch vertex together with the open paths emanating from it as branch sets: contract each subdivided edge-path to recover $H$ , so $H ≼ G$ . $□$

Proposition 2 (minor-monotonicity of tree-width). If $H ≼ G$ then $tw (H) \leq tw (G)$ .

Proof. It suffices to check the three generating operations. Start from an optimal tree-decomposition $(T, {V_{t}})$ of $G$ . Deleting a vertex $v$ : remove $v$ from each bag; the three axioms persist and no bag grows. Deleting an edge: the same decomposition still covers all remaining edges, with bags unchanged. Contracting $e = uv$ to $w$ : replace each occurrence of $u$ or $v$ in a bag by $w$ . The index sets ${t : u \in V_{t}}$ and ${t : v \in V_{t}}$ are connected subtrees that share a node (a bag containing the edge $uv$ ), so their union is connected, giving the required connected subtree for $w$ ; vertex- and edge-coverage transfer, and replacing two possibly-distinct symbols by one cannot enlarge a bag. Each operation leaves the width no larger, and $H$ arises from $G$ by a finite sequence of them, so $tw (H) \leq tw (G)$ . $□$

Proposition 3 (finite obstruction sets from wqo). Assuming $≼$ is a well-quasi-ordering of finite graphs, every minor-closed class $C$ has a finite forbidden-minor characterisation.

Proof. Let $F$ be the set of minor-minimal graphs not in $C$ : graphs $F \in / C$ all of whose proper minors lie in $C$ . First, $G \in C$ iff no $F \in F$ is a minor of $G$ . If $G \in / C$ , take a $≼$ -minimal element $F$ among the minors of $G$ that lie outside $C$ (such a minimal element exists because a wqo has no infinite descending chain); then $F \in F$ and $F ≼ G$ . Conversely if some $F \in F$ is a minor of $G$ and $G \in C$ , minor-closure would force $F \in C$ , a contradiction. Second, $F$ is an antichain: if $F_{1} ≺ F_{2}$ in $F$ then $F_{1}$ is a proper minor of $F_{2}$ lying outside $C$ , contradicting the minimality of $F_{2}$ . A wqo has no infinite antichain, so $F$ is finite. $□$

Proposition 4 (a bramble of order $> k$ forbids tree-width $< k$ ). If $G$ has a bramble of order at least $k + 1$ , then $tw (G) \geq k$ .

Proof. Let $B$ be a bramble of order $\geq k + 1$ and suppose, toward a contradiction, that $(T, {V_{t}})$ is a tree-decomposition of width $< k$ , so every bag has at most $k$ vertices. Orient each edge $s t$ of $T$ toward the side that contains a bramble member avoiding the separator $V_{s} \cap V_{t}$ : since each bag has $\leq k < k + 1 \leq ord (B)$ vertices, no single bag is a hitting set for $B$ , and standard tree-decomposition separation shows some bramble member lies entirely in one component of $T - s t$ after removing the separator; orient toward that component. A finite tree with every edge oriented has a node $t_{0}$ with all incident edges oriented inward (a sink). Every bramble member then meets the side pointed to, forcing each member to meet the bag $V_{t_{0}}$ : for any member $B$ , the inward orientations confine $B$ to be on the $t_{0}$ side of every incident edge, and since the bags along the decomposition cover $B$ and its touchings, $B$ must intersect $V_{t_{0}}$ . Thus $V_{t_{0}}$ is a hitting set of size $\leq k$ , contradicting $ord (B) \geq k + 1$ . Hence no decomposition of width $< k$ exists, i.e. $tw (G) \geq k$ . $□$

Proposition 5 (planar graphs are grid minors). Every planar graph $H$ is a minor of the $N \times N$ grid for $N$ large enough.

Proof. Fix a plane embedding of $H$ with all vertices at distinct points and edges drawn as polygonal arcs. Overlay a fine $N \times N$ grid so that each vertex of $H$ lies in the interior of a distinct grid cell and each edge-arc passes through a sequence of grid cells meeting only along the arc it follows, with distinct edges using disjoint cell sequences except at shared endpoints (possible since the embedding is a finite plane graph and the cells can be taken arbitrarily small). Form a model of $H$ in the grid by letting the branch set $B_{v}$ be the connected set of grid vertices in the cells occupied by $v$ together with the cells of the half-edges leaving $v$ , routed so that branch sets for adjacent vertices touch exactly where the corresponding edge-arc of $H$ runs and are disjoint otherwise. Each $B_{v}$ is connected (it follows a connected region of the plane), the $B_{v}$ are disjoint, and $B_{u}, B_{v}$ are joined by a grid edge iff $u \sim v$ in $H$ . So $H ≼ G_{N \times N}$ . $□$

Proposition 6 (Hadwiger's conjecture for $t \leq 4$ ). Every graph with no $K_{4}$ minor is $3$ -colourable; the cases $t = 1, 2, 3$ are immediate.

Proof. For $t = 1$ the hypothesis (no $K_{1}$ minor) forces the empty graph, $0$ -colourable. For $t = 2$ (no $K_{2}$ minor) the graph has no edge, so it is $1$ -colourable. For $t = 3$ (no $K_{3}$ minor) the graph is a forest — a cycle would contain a $K_{3}$ minor by contracting a path of the cycle — and forests are $2$ -colourable. For $t = 4$ : a graph with no $K_{4}$ minor is series-parallel, built from edges by series and parallel compositions, and such graphs have a vertex of degree at most $2$ (every series-parallel graph, being $K_{4}$ -minor-free, has tree-width at most $2$ , so it is $2$ -degenerate). Remove a vertex of degree $\leq 2$ , $3$ -colour the rest by induction, and reinsert the vertex, which has at most two coloured neighbours and so admits one of the three colours. Hence $K_{4}$ -minor-free graphs are $3$ -colourable. $□$

Connections Master

Planar graphs: Euler's formula, Kuratowski's and Wagner's theorems 40.04.05. Planarity is the prototype of every result in this unit. Wagner's theorem — planar iff no $K_{5}$ or $K_{3, 3}$ minor — is the special case of the graph-minor theorem where the obstruction set is exhibited explicitly with two elements, and Wagner's clique-sum decomposition of $K_{5}$ -minor-free graphs is the genus-zero instance of the structure theorem. This unit takes the finite-obstruction phenomenon that planarity displays concretely and proves it holds for every minor-closed class; the prerequisite owns the worked example, this unit owns the general law.
Map colouring: the four- and five-colour theorems 40.04.08. Hadwiger's conjecture is the minor-theoretic generalisation of the four-colour theorem: the case $t = 5$ is equivalent to four-colourability via Wagner's decomposition, and the case $t = 6$ (Robertson-Seymour-Thomas) again reduces to it, so the colouring unit supplies the deep input that powers the known cases of Hadwiger. Conversely Hadwiger's conjecture for general $t$ is the strongest known proposed extension of map colouring, framing the four-colour theorem as the $t = 5$ shadow of a statement about $K_{t}$ -minor-free graphs.
Graphs, basic invariants, and the foundational lemmas 40.04.01. The minor and topological-minor orders defined there are the relations this unit well-quasi-orders, and the contraction operation introduced there is the move that distinguishes minors from subgraphs. The averaging and connectivity lemmas of that unit reappear as the tools that bound tree-width and locate grid minors; this unit is the structural endpoint of the minor language that the foundational unit sets up.
Parameterised algorithms and fixed-parameter tractability 25.03.05 pending. Tree-width is the central width parameter of parameterised complexity, and the $O (n^{3})$ minor-testing algorithm makes membership in every minor-closed class fixed-parameter decidable. Bounded tree-width turns many NP-hard graph problems polynomial via dynamic programming over a tree-decomposition (Courcelle's theorem expresses this for all monadic-second-order properties), so the structural results proved here are the mathematical foundation of an entire algorithmic paradigm.

Historical & philosophical context Master

The well-quasi-ordering of trees was proved by Joseph Kruskal in 1960 in Well-quasi-ordering, the Tree Theorem, and Vázsonyi's conjecture (Transactions of the American Mathematical Society 95) ^{[Kruskal 1960]}, settling a conjecture of Andrew Vázsonyi that finite trees are well-quasi-ordered under topological embedding. Crispin Nash-Williams gave the short minimal-bad-sequence proof in 1963 (Proceedings of the Cambridge Philosophical Society 59) ^{[Nash-Williams 1963]}, the argument reproduced in the Key theorem, and the method became the standard engine of the field. Hugo Hadwiger had in 1943 proposed his colouring conjecture Über eine Klassifikation der Streckenkomplexe (Vierteljahresschrift der Naturforschenden Gesellschaft in Zürich 88) ^{[Hadwiger 1943]}, generalising the still-unproven four-colour problem to the assertion that a $K_{t}$ -minor-free graph is $(t - 1)$ -colourable.

The graph-minors project of Neil Robertson and Paul Seymour ran across twenty papers from 1983 to 2004, culminating in Graph Minors XX. Wagner's conjecture (Journal of Combinatorial Theory, Series B 92) ^{[Robertson Seymour 2004]}, which proved that finite graphs are well-quasi-ordered under the minor relation — the statement Wagner had conjectured. Along the way Graph Minors V established the excluded-grid theorem ^{[Robertson Seymour 1986]}, Graph Minors XIII gave the cubic disjoint-paths algorithm, and Graph Minors XVI proved the structure theorem for excluded minors ^{[Robertson Seymour 2003]}. The case $t = 6$ of Hadwiger's conjecture was settled by Robertson, Seymour, and Thomas in 1993. The result that membership in any minor-closed class is decidable was for a time among the few theorems proving an algorithm exists without exhibiting it, since the obstruction sets are not produced by the proof.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{West2001,
  author    = {West, Douglas B.},
  title     = {Introduction to Graph Theory},
  edition   = {2nd},
  publisher = {Prentice Hall},
  year      = {2001}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@article{Kruskal1960,
  author  = {Kruskal, Joseph B.},
  title   = {Well-quasi-ordering, the Tree Theorem, and V\'azsonyi's conjecture},
  journal = {Transactions of the American Mathematical Society},
  volume  = {95},
  year    = {1960},
  pages   = {210--225}
}

@article{NashWilliams1963,
  author  = {Nash-Williams, C. St. J. A.},
  title   = {On well-quasi-ordering finite trees},
  journal = {Proceedings of the Cambridge Philosophical Society},
  volume  = {59},
  year    = {1963},
  pages   = {833--835}
}

@article{Higman1952,
  author  = {Higman, Graham},
  title   = {Ordering by divisibility in abstract algebras},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {2},
  year    = {1952},
  pages   = {326--336}
}

@article{RobertsonSeymour1986,
  author  = {Robertson, Neil and Seymour, Paul D.},
  title   = {Graph Minors. V. Excluding a planar graph},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {41},
  year    = {1986},
  pages   = {92--114}
}

@article{RobertsonSeymour2003,
  author  = {Robertson, Neil and Seymour, Paul D.},
  title   = {Graph Minors. XVI. Excluding a non-planar graph},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {89},
  year    = {2003},
  pages   = {43--76}
}

@article{RobertsonSeymour2004,
  author  = {Robertson, Neil and Seymour, Paul D.},
  title   = {Graph Minors. XX. Wagner's conjecture},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {92},
  year    = {2004},
  pages   = {325--357}
}

@article{Hadwiger1943,
  author  = {Hadwiger, Hugo},
  title   = {\"Uber eine Klassifikation der Streckenkomplexe},
  journal = {Vierteljahresschrift der Naturforschenden Gesellschaft in Z\"urich},
  volume  = {88},
  year    = {1943},
  pages   = {133--142}
}

@article{Lovasz2006,
  author  = {Lov\'asz, L\'aszl\'o},
  title   = {Graph Minor Theory},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {43},
  year    = {2006},
  pages   = {75--86}
}

@article{RobertsonSeymourThomas1993,
  author  = {Robertson, Neil and Seymour, Paul D. and Thomas, Robin},
  title   = {Hadwiger's conjecture for $K_6$-free graphs},
  journal = {Combinatorica},
  volume  = {13},
  year    = {1993},
  pages   = {279--361}
}

Prerequisites

40.04.05

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §1.7 (contraction and minors) and the opening of §12.1 read for the picture of shrinking a connected piece to a single dot; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §6.1 for the minor / subdivision vocabulary on small drawings; Robertson-Seymour's expository accounts of the graph-minors project for the 'finitely many forbidden patterns' slogan
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §12.1 (well-quasi-ordering, Kruskal's tree theorem) and §12.3-§12.4 (tree-width and tree-decompositions, the duality with brambles); West 2001 §6.1; Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 10 (planarity and the minor order as background)
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 12 in full (§12.4 brambles and tree-width duality, §12.5 the excluded-grid theorem, §12.6 the structure theorem for graphs with an excluded minor, the graph-minor theorem and its algorithmic consequences); Lovász 2006 *Graph Minor Theory* (Bull. AMS 43) for the survey; the original Robertson-Seymour *Graph Minors* series I-XX (1983-2004), in particular XIII (the disjoint-paths algorithm), XVI (the structure theorem), XX (Wagner's conjecture); Kruskal 1960 and Nash-Williams 1963 for well-quasi-ordering

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 12 (§12.1 well-quasi-ordering and Kruskal's tree theorem; §12.3 tree-width and tree-decompositions; §12.4 brambles and the tree-width duality theorem; §12.5 the excluded-grid theorem; §12.6 the structure theorem for graphs excluding a minor and the graph-minor theorem)
Lovász 2006 — Graph Minor Theory · Bulletin of the American Mathematical Society 43 (2006) 75-86; survey of the Robertson-Seymour structure theory, tree-width, and the excluded-grid theorem
Kruskal 1960 — Well-quasi-ordering, the Tree Theorem, and Vázsonyi's conjecture · Transactions of the American Mathematical Society 95 (1960) 210-225; trees are well-quasi-ordered under topological minor (embeddability)
Nash-Williams 1963 — On well-quasi-ordering finite trees · Proceedings of the Cambridge Philosophical Society 59 (1963) 833-835; the minimal-bad-sequence proof of Kruskal's theorem
Robertson, Seymour 2004 — Graph Minors. XX. Wagner's conjecture · Journal of Combinatorial Theory, Series B 92 (2004) 325-357; finite graphs are well-quasi-ordered under the minor relation
Robertson, Seymour 1986 — Graph Minors. V. Excluding a planar graph · Journal of Combinatorial Theory, Series B 41 (1986) 92-114; the excluded-grid theorem relating tree-width to grid minors
Robertson, Seymour 2003 — Graph Minors. XVI. Excluding a non-planar graph · Journal of Combinatorial Theory, Series B 89 (2003) 43-76; the structure theorem for graphs with a fixed excluded minor (surface, vortices, apex)
Hadwiger 1943 — Über eine Klassifikation der Streckenkomplexe · Vierteljahresschrift der Naturforschenden Gesellschaft in Zürich 88 (1943) 133-142; the conjecture that a graph with no K_t minor is (t-1)-colourable

Estimated time

beginner: 18m
intermediate: 48m
master: 90m