Episode 157, October 2026

Hadwiger disproved?

Three preprints claim graphs that need more colours than their largest clique minor, a second disproof through Colin de Verdière’s invariant, and a linear bound that survives

Covers result 157 in OpenAI’s catalog: all 3 papers. See its connections to other results and the work it cites.

Play Episode 157: Hadwiger disproved? Two bars: the Hadwiger number h, shorter than the chromatic number chi.

6:47. English captions available. The video loads from YouTube when you press play.

Chapters

The claims, in plain words

Colour the vertices of a graph so that neighbours differ. A clique minor of order t is a set of t disjoint, connected blobs of vertices, every two joined by an edge; the Hadwiger number h(G) is the largest such t. “Hadwiger’s conjecture, formulated in 1943, asserts that h(G) ≥ χ(G) for every finite nonempty simple graph G.” As the paper recounts, the cases t = 4 (Hadwiger, Dirac), t = 5 (equivalent to the Four-Colour Theorem, through Wagner’s structure theorem) and t = 6 (Robertson, Seymour and Thomas) were proved, and general bounds went down to O(t log log log t) in a 2026 preprint by Liu and Luo. If no three vertices are pairwise non-adjacent (independence number at most two), each colour is used at most twice, so a graph on m vertices needs at least m/2 colours, even fractionally; Duchet and Meyniel guarantee a clique minor of order m/3.

Result 157 lists three OpenAI preprints dated September 23, 2026. A counterexample to Hadwiger’s conjecture (104 pages) claims arbitrarily large graphs on m vertices with independence number at most two and no connected matching of m/100 edges, so that h(G) < 26m/75 + 2/3 < m/2 ≤ χ_f(G) ≤ χ(G): Hadwiger’s conjecture, and the fractional weakening discussed by Reed and Seymour, are false. Reed and Seymour’s proven bound χ_f ≤ 2h stands; by our arithmetic these graphs show the factor is at least about 1.44.

A counterexample to the Colin de Verdière chromatic conjecture (131 pages) claims graphs with μ(G) + 1 < |V(G)|/2 ≤ χ(G), where μ is Colin de Verdière’s spectral invariant. Since h ≤ μ + 1, Hadwiger’s conjecture would imply χ ≤ μ + 1, so this is a second disproof, on similar random graphs with a different final argument (a matrix-rank obstruction); it claims no real gap beyond χ > μ + 1. A linear list-coloring bound in terms of the Hadwiger number (42 pages) claims that a constant factor survives: χ_list(G) ≤ C·h(G), and so χ(G) ≤ C·h(G), for one absolute integer C that is never computed (any such constant must be at least 2).

What they don’t claim

The graphs are random samples, not explicit, and no smallest example or effective threshold is given; by the paper’s own formulas the number of vertices has more than 10³⁰ digits (our arithmetic). The papers do not say which order t fails first; the cases t = 4, 5 and 6 remain theorems. It is not the first disproof of a Hadwiger-type conjecture: the Hadwiger paper credits a December 2025 preprint by Kühn, Sauermann, Steiner and Wigderson for the odd Hadwiger conjecture, and the list paper cites Barát, Joret and Wood’s 2011 “Disproof of the list Hadwiger conjecture”. None of the papers calls the problem famous or long-standing. Hadwiger’s conjecture is unrelated to the Hadwiger–Nelson problem of colouring the plane (result 158).

Where it stands

Posted as preprints: OpenAI, 104, 131 and 42 pages, dated September 23, 2026
Peer reviewed: Not yet
Checked in Lean: Two of three: the ordinary Hadwiger counterexample and the list bound. We have not rebuilt them

Last checked October 19, 2026. The preprints have not been revised since they were added to the repository in its initial commit on October 6, 2026, though the list paper, dated September 23, cites work posted on October 1. OpenAI published Lean formalizations of two statements: the Hadwiger counterexample for ordinary colouring (comparator: independence number at most two, connected matchings below m/100, and h < 26m/75 + 2/3 < m/2 ≤ χ; not the fractional form), added in the October 7 commit, with 288 files and 39,776 lines of proof; and the list bound in full (comparator), with 53 files and 19,965 lines, which also proves the three structural results the paper cites without proof. Both counts exclude Mathlib, and we found no unproved steps. We have not rebuilt them. The Colin de Verdière paper is not formalized, apart from a small support file of conditional lemmas. None of the papers is among those OSVerify reviewed, and we have seen no expert review.

How the proofs go

From clique minors to matchings. In a clique minor, blobs of three or more vertices are expensive. Single-vertex blobs are pairwise adjacent, so they pair up into edges, and two-vertex blobs are edges already; all these edges touch pairwise, forming a connected matching. Counting gives h(G) ≤ (m + 4cm(G) + 2)/3 (Proposition 3.5), so graphs with independence number at most two and cm < m/100 have h < 26m/75 + 2/3.
Holes that never form a triangle. Vertices are random objects of linear algebra over the field with two elements; two are non-adjacent (a hole) when a short list of linear identities, built from a symmetric bilinear form and including a parity condition, can be met. Summed around a hypothetical triangle of holes, everything cancels except the parity bits, leaving 0 = 1, so the independence number is at most two for every sample. Two disjoint edges fail to touch exactly when all four cross pairs are holes; about eighty pages (Theorem 3.1) show that such conflicts cannot be avoided, and a container-style counting argument makes every connected matching smaller than m/100 with high probability.
The other two papers. The Colin de Verdière paper replaces each vertex of a similar random graph by a clique, which keeps the colouring bound, and shows that every well-signed matrix with one negative eigenvalue has rank greater than half the number of vertices plus one. The list paper handles small graphs by removing random independent sets, starting from Reed and Seymour’s fractional bound, and large graphs by extracting highly connected pieces and building the clique minor in a three-way recursion; it cites three structural results without proof.

The numbers in the video

Our check: all 172 graphs on up to 7 vertices with no three pairwise non-adjacent vertices, and 108 random ones on 8 to 16 vertices, satisfy h ≥ χ (with equality in 113 and 29 of them). Complements of C₅, C₇, C₉, the Petersen, Grötzsch, Chvátal and Heawood graphs: (χ, h) = (3, 3), (4, 5), (5, 6), (5, 6), (6, 6), (6, 7), (7, 9).
Proposition 3.5 holds on all 1,252 graphs up to 7 vertices, with equality only for K₁, K₃, K₅, K₇ (our check).
The hole relation in small models over the field with two elements (ours): no triangles under the paper’s hypotheses; 58,240 with a non-symmetric form.
(1 + 4/100)/3 = 26/75; 26m/75 + 2/3 < m/2 from m = 5; the ratio (m/2)/(26m/75) tends to 75/52 ≈ 1.44 (our arithmetic).

Read the source

A counterexample to Hadwiger’s conjecture (PDF), 104 pages.
A counterexample to the Colin de Verdière chromatic conjecture (PDF), 131 pages.
A linear list-coloring bound in terms of the Hadwiger number (PDF), 42 pages.
The Lean scope note.
The collection’s catalog, where this is result 157.

The 3 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

A counterexample to Hadwiger's conjecture main paper
A counterexample to the Colin de Verdière chromatic conjecture companion
A linear list-coloring bound in terms of the Hadwiger number companion

Transcript

Read the full script

0:00Colours and clique minors

Colour the vertices of a graph so that neighbours always get different colours. A clique minor of order t is a set of t disjoint, connected blobs of vertices, every two of them joined by an edge; squeeze each blob to a point and you see t vertices, all joined to each other. In 1943, Hadwiger conjectured that a graph needing t colours always contains a clique minor of order t. As the paper recounts, this was proved for four; for five, where it is equivalent to the four colour theorem; and for six, by Robertson, Seymour and Thomas. For general t, the paper cites bounds of t times a slowly growing factor; the most recent, in a 2026 preprint, involves a triple logarithm. One special case is cleaner. If no three vertices are pairwise non-adjacent, each colour can be used at most twice, so a graph on m vertices needs at least m/2 colours, even when colours may be split fractionally. The conjecture then asks for a clique minor of order half the vertices; known results, the paper notes, guarantee about a third. In our check of every such graph up to 7 vertices, and of about 100 random ones up to 16, the conjecture held, often exactly. Weaker forms were also studied. Reed and Seymour proved that a fractional colouring with twice the Hadwiger number of colours always exists. And a linear list version, formulated by Kawarabayashi and Mohar, asks whether some constant multiple of the Hadwiger number suffices even when each vertex has its own list of allowed colours. With the constant equal to one, that list version was already known to fail, and any such constant must be at least two.

1:44The claims

Result 157 lists three OpenAI preprints, all dated September 23. The first, 104 pages long, claims that, for arbitrarily large m, there are graphs on m vertices, with no three pairwise non-adjacent vertices, whose largest clique minor has order below 26m/75 + 2/3. That is below m/2, so these graphs need more colours than their Hadwiger number, even fractionally. This disproves Hadwiger’s conjecture, and the fractional form that Reed and Seymour discussed. Their proven factor of two still stands; by our arithmetic, these graphs show the factor cannot be below about 1.44. The second, 131 pages long, disproves Colin de Verdière’s proposed bound: chromatic number at most his spectral graph invariant, μ, plus one. Since the Hadwiger number is at most μ + 1, Hadwiger’s conjecture would imply that bound, so this is a second disproof, on similar random graphs but with a different final argument, though it claims no real gap: only that the chromatic number exceeds mu plus one. The third, 42 pages long, shows that a constant factor does survive: for one absolute constant C, never computed, the list chromatic number is at most C times the Hadwiger number, and so is the ordinary chromatic number. The graphs are random, not explicit. No smallest example is given, and by the paper’s own formulas the number of vertices has more than 10³⁰ digits. The paper does not say which order t fails first; the cases four to six still stand. And it is not the first disproof of a Hadwiger-type conjecture: the paper credits a 2025 preprint for the odd version, and, as the third paper cites, the list Hadwiger conjecture had already been disproved in 2011.

3:42How the proofs go

The first paper’s proof turns minors into matchings. In a large clique minor, blobs of three or more vertices are expensive. Single-vertex blobs are all joined to each other, so they pair up into edges, and two-vertex blobs are edges already; all these edges touch each other pairwise, forming a connected matching. Counting gives a bound: the Hadwiger number is at most m, plus four times the largest connected matching, plus two, all over three. So it suffices to build graphs with no three pairwise non-adjacent vertices, whose connected matchings have fewer than m/100 edges. The vertices are random objects from linear algebra over the field with two elements. Two vertices are non-adjacent, a hole, when a short list of linear identities can be met, including a parity condition. Summed around a hypothetical triangle of holes, everything cancels except the parity bits, leaving one equals zero. So no three vertices are pairwise non-adjacent, for every sample. In our small version of this rule, holes never formed a triangle; with a non-symmetric form in place of the paper’s symmetric one, they formed 58,240. Two matching edges fail to touch exactly when all four cross pairs are holes. About eighty pages show that such conflicts cannot be avoided, and a counting argument then makes every connected matching smaller than m/100, with high probability. The second paper replaces every vertex of a similar random graph by a clique, which keeps the colouring bound, and shows that every matrix allowed in the definition of μ has rank greater than half the number of vertices, plus one. The third paper handles small graphs by repeatedly removing random independent sets, starting from Reed and Seymour’s fractional bound, and large graphs by extracting highly connected pieces and building the clique minor in a three-way recursion. It cites three structural results without proof.

5:44Where it stands

None of the three is peer reviewed, and the preprints have not been revised, though the third, dated September 23, cites work posted on October 1. OpenAI’s Lean formalizations cover the first paper’s ordinary statement, added a day after the repository’s first commit, in 288 files and about 40,000 lines; and the third paper’s theorem in full, in 53 files and about 20,000 lines, including the three results it cites. We found no unproved steps in either, and we have not rebuilt them. The fractional statements and the second paper are not formalized, apart from a small support file. None of the papers is among those OSVerify reviewed, and we have seen no expert review. If they hold, Hadwiger’s conjecture is false, but only by a constant factor: the number of colours a graph needs is still controlled by its largest clique minor, up to a constant.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.