Hadwiger's Conjecture

For a graph $G$ let $h(G)$ , the Hadwiger number, be the largest $t$ such that $K_t$ is a minor of $G$ . Hadwiger (1943) conjectured that every graph with no $K_{t+1}$ minor is $t$ -colourable, that is, $\chi(G)\le h(G)$ . It was known for $t\le5$ (Hadwiger and Dirac for $t=3$ , Wagner plus the Four Colour Theorem for $t=4$ , Robertson-Seymour-Thomas for $t=5$ ). The special case of graphs with independence number at most two (equivalently, every such $m$ -vertex graph has a $K_{\lceil m/2\rceil}$ minor, Plummer-Stiebitz-Toft) and the fractional weakening $\chi_f(G)\le h(G)$ discussed by Reed and Seymour (1998) were also open. Does every finite graph satisfy $\chi(G)\le h(G)$ ?

Result: Disproved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Construction
Field: Graph coloring and graph minors
Posed by: Hugo Hadwiger, Uber eine Klassifikation der Streckenkomplexe, Vierteljahrsschr. Naturforsch. Ges. Zurich 88 (1943); fractional weakening discussed by Reed and Seymour (1998)
Year posed: 1943
Years open: 83y
Solved: 2026-09-23
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Unreviewed
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 70 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: there are arbitrarily large $m$ and $m$ -vertex graphs with $\alpha(G)\le2$ and connected-matching number below $m/100$ . With the counting bound $h(G)\le(|V(G)|+4\,\mathrm{cm}(G)+2)/3$ , Corollary 1.2 gives $h(G)<26m/75+2/3<m/2\le\chi_f(G)\le\chi(G)$ . So Hadwiger's conjecture fails, already in the case $\alpha\le2$ and even for fractional colouring, with $\chi/h$ above about $1.44$ in the limit. The graphs are complements of a triangle-free hole relation built from tensor frames over $\mathbb F_2$ , so $\alpha\le2$ ; the four-hole conflicts that kill large connected matchings are forced by a distribution theorem and a container argument. It does not say anything about small $t$ , and it does not refute linear bounds $\chi\le C\,h$ , which the companion list-colouring paper proves.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction, historical section and Theorem 1.1 with Corollary 1.2, read against Hadwiger's conjecture as cited (Hadwiger 1943) and the Reed-Seymour fractional weakening. The probabilistic and algebraic construction was not refereed. formalization.yaml lists no main result for this manuscript; the Lean doc for the family covers only the list-colouring companion. The counterexamples are shown to exist only for sufficiently large order; no explicit graph is given. The companion Colin de Verdiere paper gives a second, independent route to graphs with chromatic number above the Hadwiger number.

Hadwiger's Conjecture

What was actually shown

What the AI did

Verification

Sources

Discussion