AN AI CRACKS A COLOURING PUZZLE

Take a network of dots joined by lines — what mathematicians call a graph. Now colour the dots so that two dots joined by a line never have the same colour. The smallest number of colours that works is the graph’s chromatic number. A famous special case is the four-colour theorem, proved in 1977, whose title says it all: “Every planar map is four colorable.”

Hadwiger’s 1943 bet

In 1943, Hadwiger proposed a sweeping rule for all graphs. Shrink a graph by deleting dots or lines, and by merging two linked dots into one. The result is called a minor. Hadwiger looked at the largest complete graph — a cluster in which every dot is linked to every other — that can be obtained this way, and conjectured that the number of colours needed never exceeds the size of that cluster.

The paper calls it “amongst the oldest and most fundamental problems in graph theory.” It is proven only for small cases: up to clusters of five, where it turns out to be equivalent to the four-colour theorem or reducible to it. From six onward, it is open.

Getting close, one logarithm at a time

Since the exact statement resists, researchers tried to bound the number of colours by some function of the cluster size, growing as slowly as possible. The paper recounts the progress. For decades, the best bound grew slightly faster than proportionally — by a factor involving the square root of a logarithm. A few years ago, Norin, Postle and Song broke that barrier. Delcourt and Postle then improved it further and, crucially, showed that it is enough to deal with fairly small graphs. Liu and Luo pushed the extra factor down to a triple logarithm.

The natural end point is the linear Hadwiger conjecture: a fixed multiple of the cluster size is always enough. That is what Sergey Norin, of McGill University in Montreal, and Raphael Steiner, of ETH Zurich, now claim to prove.

The part played by the machine

The authors are explicit: the proof was found by GPT-6 Astra, an OpenAI model, following their directions. They first asked it to prove the case of very dense graphs, which they believed was the missing piece. It succeeded, they write, “after only a couple of hours and some encouragement.” Asked to make one dependence explicit, it covered graphs up to a certain size — but not quite the range needed. They then asked it for an original idea to bridge the gap, which produced the “bootstrap” step of the final proof. Almost none of the authors’ own specific proof ideas survived, they say, apart from one suggestion about contractions.

The writing is human. Another OpenAI model helped with proofreading and the bibliography. The authors report that OpenAI’s Codex produced a formal, machine-checkable version of the whole proof in the Lean proof assistant, posted online alongside an early AI-written draft. They take full responsibility for the mathematics.

Inside the proof

The argument has two halves:

1. Small graphs, few colours. For graphs not much larger than the cluster limit, the authors show that about four times the cluster size suffices. The starting point is a 1998 result of Reed and Seymour: a relaxed, “fractional” form of colouring already obeys the linear rule with factor two. The new work turns fractional colourings into real ones by adding a few extra lines to the graph and finding huge matchings in an auxiliary structure.
2. A bootstrap. A second argument extends the range of graph sizes covered by a factor of four-thirds in the exponent at each step, at the cost of a larger constant. Ten steps take the range from one third to about 5.92, past the threshold of 5 required by the Delcourt-Postle reduction. This half uses an old trick due to Gyárfás, which the authors say had never been applied to this problem.

The authors describe the proof as built from known tools — “contained in the convex hull of existing results,” yet not on an obvious edge of it.

What remains open

The constant is enormous: a rough estimate gives about 10¹⁰⁰. The authors see room to bring it below 10¹⁰, but think reaching, say, 100 would need new ideas. Hadwiger’s exact conjecture is untouched: “We are undecided,” they write. The paper is a preprint; 41 pages of new mathematics will now face the scrutiny of other experts.