Graph minor
Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.
Five spokes squeezed into K5
The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.
Seven graphs that must link
Six points joined in every way cannot be placed in space without two disjoint triangles hooking together. Trade any triangle for a three-pointed star, or a star back for a triangle, and the property survives; doing it in every possible way from K₆ reaches exactly seven graphs, the Petersen graph among them, and stops. Every placement of every one of them links, by the same parity count. Remove any edge from any of them, and placements that link nothing appear at once. The seven are the whole answer: a graph must link exactly when it contains one of them.
The order that keeps elimination narrow
Eliminating letters one at a time costs whatever the widest step costs, and the least width any order can achieve is the treewidth of the formula's graph. Finding it exactly is NP-hard, but a search over sets of letters instead of sequences finds it for small graphs, and a greedy rule that adds the fewest new edges finds it on 566 of 600 random graphs and misses by more than one only once. On Tseitin's 6 × 6 grid that rule forms twenty-four times fewer resolvents than sweeping row by row. What it cannot do is prove that its order is the best.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchComplete graphDecompositionDelta y exchangeEuler formulaGraphGraph colouringGreedy algorithmIntrinsically linkedLinking numberLower boundNP-hard