Decomposition
Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.
A labelling every tree seems to have
Number the points of a tree 0 to n − 1 and write on each edge the difference of the numbers at its ends. The labelling is graceful if the edges then carry 1 to n − 1, each exactly once. Every tree anyone has ever checked — every one of the 551 trees on twelve points, and every tree up to about thirty-five — has such a labelling, and no one knows why. A graceful tree also tiles a complete graph by rotation, which is why the question was asked.
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 graphConjectureGraphGraph labellingGraph minorGreedy algorithmLower boundNP-hardRandom graphResolutionSatisfiability