Automating the Search for Graph-Theoretic Proof with Grok 4.5
An autonomous attempt on the great unsolved conjectures of graph theory — continuous, unattended, and published unedited.
Abstract
Grok ConjectureGraph theory is unusually rich in conjectures that are simple to state, believed by nearly everyone, and stubbornly unproved for half a century. Reconstruction, Hadwiger, the graceful trees — each has absorbed decades of concentrated attention and returned only partial results, and the barriers are now understood well enough that the field can say precisely why the obvious approaches cannot close them. That makes it a clean setting in which to ask what a foundation model actually contributes to open mathematics: the answer is not obscured by low-hanging fruit, because there is none.
The question is no longer hypothetical. A roughly thirty-year-old graph conjecture was recently reported resolved with model assistance — the The Erdős–Gyárfás Conjecture sits in our set marked disputed, because a headline is not a proof and verification is still underway. Grok Conjecture treats that not as an endpoint but as a reason to instrument the process properly.
The system runs a continuous, unattended attempt on these problems. Grok 4.5 is given the formal statement, the documented obstruction, and a registered attack surface drawn from the literature, and is asked for a checkable increment — a lemma, a sharpened bound, a labelling that works, or a precise account of where an approach breaks. It is explicitly forbidden to claim a proof, and required to label every step [ESTABLISHED], [DERIVED], or [CONJECTURAL]. Transcripts are published unedited.
The honest expected outcome is failure, at very high probability, on every run. That is worth instrumenting anyway. The interesting measurement is not whether the model resolves a famous conjecture — it almost never will — but whether the distribution of its failures carries signal: whether it rediscovers a known obstruction unprompted, judges which of two dead ends is less dead, and whether a solved control problem is genuinely reconstructed or merely recited. The last of these is the primary guard against mistaking retrieval for reasoning.
Long-horizon inference is expensive and the schedule is open-ended, so the compute is funded structurally rather than by grant: creator fees from the $GROK canonical pool are routed into the inference budget. The mechanism is described in full, including the parts that work against us.
Conjectures tracked
9
7 still open
Oldest open
1942
Reconstruction, unproved since
Inference
Grok 4.5
continuous, unattended
Peak creator fee
0.95%
canonical pool, per trade
§1
The increment protocol
A run does not attempt the whole conjecture. It attempts one registered entry from that problem's attack surface, and is scored on whether the increment is checkable — not on whether it is impressive. The instruction that does the most work is the one forbidding a claimed proof: a model permitted to conclude triumphantly will do so, and the output becomes unfalsifiable prose. Forced to name the step it cannot justify, it produces something a referee can act on.
Take Hadwiger's Conjecture — that a graph needing colours must contain as a minor. It is stated to the solver alongside its documented floor: the case is equivalent to the Four Colour Theorem, so no elementary argument can reach it. A run commits to one sub-goal and says why.
Every run carries the same failure mode: the model reproduces a known argument, hits the known wall, and describes the wall. That is the expected output and it is recorded as such. The rare interesting case is a run that reaches the wall by a route the literature does not take.
§2
The memorisation control
Ringel's Conjecture (1963)is in the problem set despite having been settled — proved for all sufficiently large trees by Montgomery, Pokrovskiy and Sudakov in 2020. It is the control. Its proof is recent and well documented, so a model asked to “solve” it can succeed by recall alone — which makes it the one problem where we can distinguish reconstruction from recitation and calibrate everything else against the result.
A run is scored as reconstruction only if it rebuilds the absorption argument rather than quoting it, explains why a purely greedy edge-disjoint embedding stalls, and identifies why the count is copies and not . Recitation is common. Reconstruction is not.
§3
Funding the schedule
An open-ended attempt needs an open-ended compute budget. Every trade of $GROK splits into a creator fee, a protocol fee, and an LP fee. On the bonding curve that split is fixed at 0.3% / 0.95% / 0%. Once the coin graduates it holds a canonical pool on PumpAMM, and the schedule becomes a step function of market cap — the creator share rises to 0.95% in the first band above the curve, then decays monotonically through 25 bands to a floor of 0.05%.
The consequence is worth stating plainly rather than burying: creator revenue is a function of volume, and the rate falls as the coin appreciates. A large, quiet market cap funds very little. The full schedule in both denominations is set out in PumpAMM.
Watch it work in real time
The solver cycles the conjectures on its own, continuously — every problem under attack at once. Read the reasoning as it arrives. Nothing is filtered and nothing is retried; the first pass is what gets published.