Introduction

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.

Pull a K5 Out of the Graph

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">This graph hides a <b>K5</b> minor — five groups of vertices, every pair linked. Click an edge to select it, then <b>Contract</b> to merge its two endpoints into one super-vertex, or <b>Delete</b> to remove it. Reach five super-vertices that are all pairwise connected and you've pulled out a K5.</p>
<svg id="graph" viewBox="0 0 320 300" aria-label="graph"></svg>
<div class="status" id="status">Select an edge to begin.</div>
<div class="btns">
  <button id="contract" type="button">Contract edge</button>
  <button id="delete" type="button">Delete edge</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Graph-minor extraction. We start from a graph that CONTAINS a K5 minor but is not itself K5: it has 5 "core" vertices forming a near-complete graph, plus an extra vertex 5 that sits on the path between cores 0 and 4, plus one redundant edge. The player must CONTRACT to merge the extra vertex into a core (restoring the missing direct link) and may DELETE leftover edges. A K5 minor is exposed when the contracted graph has exactly 5 super-vertices that are pairwise adjacent.
//
// Minor operations on a simple graph:
//   delete(u,v)   : remove the edge
//   contract(u,v) : merge v into u; reroute v's edges to u; drop self-loops & parallels
const START = {
  // positions for layout (id -> [x,y])
  pos: { 0:[160,40], 1:[280,120], 2:[235,260], 3:[85,260], 4:[40,120], 5:[100,150] },
  // initial edges (undirected, stored as "min,max")
  edges: [[0,1],[0,2],[0,3],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[4,5],[5,0],[5,3]]
};

let nodes, adj, members, selected;
const svg = document.getElementById('graph');

function key(a,b){ return a<b ? a+','+b : b+','+a; }

function init(){
  nodes = Object.keys(START.pos).map(Number);
  members = {}; nodes.forEach(n => members[n] = [n]); // which original ids each super-node holds
  adj = {}; nodes.forEach(n => adj[n] = new Set());
  START.edges.forEach(([a,b]) => { adj[a].add(b); adj[b].add(a); });
  selected = null;
  render();
  setStatus('Select an edge to begin.', '');
}

function pos(n){
  // a super-node sits at the average of its members' original positions
  const ms = members[n]; let x=0,y=0;
  ms.forEach(m => { x += START.pos[m][0]; y += START.pos[m][1]; });
  return [x/ms.length, y/ms.length];
}

function edgeList(){
  const out = []; const seen = new Set();
  nodes.forEach(u => adj[u].forEach(v => { const k = key(u,v); if(!seen.has(k)){ seen.add(k); out.push([Math.min(u,v),Math.max(u,v)]); } }));
  return out;
}

function render(){
  svg.innerHTML = '';
  // edges
  edgeList().forEach(([a,b]) => {
    const [x1,y1]=pos(a), [x2,y2]=pos(b);
    const ln = document.createElementNS('http://www.w3.org/2000/svg','line');
    ln.setAttribute('x1',x1); ln.setAttribute('y1',y1); ln.setAttribute('x2',x2); ln.setAttribute('y2',y2);
    ln.setAttribute('class','edge'+(selected && key(a,b)===selected ? ' sel':''));
    ln.addEventListener('click',()=>{ selected = key(a,b); render(); setStatus('Edge selected. Contract or delete it.',''); });
    svg.appendChild(ln);
  });
  // nodes
  nodes.forEach(n => {
    const [x,y]=pos(n);
    const c = document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx',x); c.setAttribute('cy',y); c.setAttribute('r',16); c.setAttribute('class','node');
    svg.appendChild(c);
    const t = document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x',x); t.setAttribute('y',y); t.setAttribute('class','node-label');
    t.textContent = members[n].slice().sort((a,b)=>a-b).join('');
    svg.appendChild(t);
  });
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function selectedPair(){
  if(!selected) return null;
  const [a,b] = selected.split(',').map(Number);
  if(adj[a] && adj[a].has(b)) return [a,b];
  return null;
}

function del(){
  const p = selectedPair();
  if(!p){ setStatus('Select an edge first.','bad'); return; }
  const [a,b]=p; adj[a].delete(b); adj[b].delete(a); selected=null; render(); checkWin('Edge deleted.');
}

function contract(){
  const p = selectedPair();
  if(!p){ setStatus('Select an edge first.','bad'); return; }
  const [u,v]=p; // merge v into u
  adj[v].forEach(w => { if(w!==u){ adj[u].add(w); adj[w].add(v); adj[w].delete(v); adj[w].add(u); } });
  adj[u].delete(v); // drop the contracted edge / self-loop
  members[u] = members[u].concat(members[v]);
  delete adj[v];
  nodes = nodes.filter(n => n!==v);
  selected=null; render(); checkWin('Edge contracted.');
}

// K5 minor exposed <=> exactly 5 super-vertices, all pairwise adjacent (10 edges).
function isK5(){
  if(nodes.length !== 5) return false;
  for(let i=0;i<nodes.length;i++) for(let j=i+1;j<nodes.length;j++)
    if(!adj[nodes[i]].has(nodes[j])) return false;
  return true;
}

function checkWin(prefix){
  if(isK5()) setStatus('K5 minor exposed — five super-vertices, all pairwise linked!','ok');
  else if(nodes.length < 5) setStatus(fmt('%prefix% Too few vertices now — you contracted too much. Reset to retry.', { prefix: prefix }),'bad');
  else setStatus(fmt('%prefix% Keep going: reach 5 vertices that are all pairwise connected.', { prefix: prefix }),'');
}

document.getElementById('contract').addEventListener('click',contract);
document.getElementById('delete').addEventListener('click',del);
document.getElementById('reset').addEventListener('click',init);
init();
Result
Console

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.

The Real Complexity

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(n3)O(n^{3}) time for a fixed H (later improved to O(n2)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/graph-minors/Content licensed under CC BY-NC 4.0.