Graph Minors

Take any network — a road map, a circuit, a molecule — and start simplifying it. You can delete an edge, delete a lonely vertex, or contract an edge by gluing its two endpoints into one. Whatever graph you can reach this way is called a minor of the original.

It sounds like idle doodling. But hidden inside this one operation is a structure so rich that proving its central fact took Neil Robertson and Paul Seymour more than twenty papers and two decades, settling a question — Wagner's conjecture — that had stood open since the 1930s.

The punchline is stranger than a hard problem. The theorem proves that fast algorithms exist for an enormous class of questions — and then, maddeningly, refuses to tell you what those algorithms are.

Here is a graph that secretly contains K5 — the complete graph on five vertices, where all five are pairwise connected. Your job is to expose it using only two moves: delete an edge you don't need, or contract an edge to merge its endpoints into a single super-vertex.

<p class="hint">{{hint}}</p>
<svg id="graph" viewBox="0 0 320 300" aria-label="{{aria_graph}}"></svg>
<div class="status" id="status">{{status_begin}}</div>
<div class="btns">
  <button id="contract" type="button">{{btn_contract}}</button>
  <button id="delete" type="button">{{btn_delete}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
svg { width: 100%; max-width: 320px; height: auto; display: block; margin: 0 auto; touch-action: manipulation; }
.edge { stroke: #8a93a0; stroke-width: 3; cursor: pointer; }
.edge:hover { stroke: #1d3557; }
.edge.sel { stroke: #e63946; stroke-width: 5; }
.node { fill: #1d3557; stroke: #fff; stroke-width: 2; }
.node-label { fill: #fff; font: 700 11px ui-monospace, monospace; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry between finding and checking. Once you have five blobs that are all pairwise linked, verifying it is a K5 minor is instant — just look. Finding the right sequence of deletions and contractions is the search. The Robertson-Seymour theorem is about the deep end of this: testing whether any fixed pattern is a minor turns out to be doable in polynomial time — but the proof never hands you the recipe.

Here is the theorem, and why it bends the usual rules.

• A family is minor-closed if, whenever it contains a graph, it also contains every minor of that graph. Planar graphs are an example: shrink a planar graph and it stays planar.
• The Robertson-Seymour theorem (proved). Across a 20-paper series from 1983 to 2004, Neil Robertson and Paul Seymour proved Wagner's conjecture: every minor-closed family can be characterized by a finite list of forbidden minors — a graph belongs to the family if and only if it contains none of them as a minor. (For planar graphs that list is famously just two graphs, K5 and K3,3, by Wagner's earlier theorem.)
• It implies a fast test. Robertson and Seymour also proved you can test "is H a minor of G?" in $O(n^{3})$ time for a fixed H (later improved to $O(n^{2})$). Combine the two facts: any minor-closed property can be decided in polynomial time by checking a finite obstruction set. The property is even fixed-parameter tractable.
• But the proof is nonconstructive. This is the twist. The theorem guarantees the finite forbidden-minor list exists, but gives no way to compute it and no bound on how big it is. The polynomial-time algorithm is real, yet for most families nobody can write it down, and its hidden constants are astronomical — galactic algorithms that are useless in practice.

That is the unsettling lesson: a fully proven theorem can certify that an efficient algorithm exists while leaving you with literally no algorithm to run. Existence and construction, which our intuition treats as the same thing, come apart — much as they do around P vs NP.

Minors are not a curiosity — they organize a huge swath of algorithm design:

• Planarity and embedding. Whether a circuit or network can be drawn without crossings is a minor question: it is planar exactly when it avoids K5 and K3,3 as minors.
• Parameterized algorithms. Treewidth, branchwidth and the whole toolkit of fixed-parameter tractability lean on minor structure to solve otherwise hard problems fast when a graph is "tree-like."
• The structure theorem. Robertson and Seymour's decomposition of minor-free graphs is the engine behind modern approximation and routing algorithms.
• Knowing a shortcut exists. Sometimes the mere guarantee from the theorem tells researchers a polynomial algorithm is out there, pointing them toward an explicit one they can actually build.

The same tension shows up across complexity: like graph coloring, graph problems are easy to state and deceptively deep, and knowing a problem is tractable is a world apart from holding the algorithm in your hand.

Deleting and contracting edges seems like the humblest thing you can do to a graph. Yet the Robertson-Seymour theorem turns it into one of the deepest results in mathematics: every minor-closed family hides behind a finite wall of forbidden patterns, and crossing that wall can be tested quickly.

The catch is what makes it unforgettable. The proof is nonconstructive — it promises the patterns and the fast algorithm exist, but it won't tell you the patterns, won't bound their size, and leaves the "efficient" algorithm with constants no machine could survive. It is a rare and humbling kind of knowledge: a theorem that proves a door is unlocked while keeping the key, a cousin of the deeper mysteries around P vs NP.