Search

Graph coloring, clique minors, and Colin de Verdière invariants

Proves Hadwiger's 1943 coloring conjecture is false, and that a fixed multiple of the minor size still bounds coloring.

3 papers September 23, 2026 Explained by AI

Hadwiger guessed in 1943 that a graph needing k colors must contain a complete graph on k vertices as a minor. The first paper builds arbitrarily large graphs that break this guess, with room to spare. The third paper shows the guess is only off by a constant factor, even when each vertex has its own list of allowed colors. A computer proof checker has formal versions of both results. The second paper claims a counterexample to a related conjecture of Colin de Verdière, which has no Lean check.

First step
1943
Hugo Hadwiger, conjecture that the chromatic number is at most the Hadwiger number
Significance
Landmark
It disproves one of the best-known conjectures in graph theory, and Lean has formal statements of the counterexample and the linear replacement bound.
Trust
Formal proof listed
Field
Combinatorics
3 papers

The explanation

Take a cycle of five vertices, a pentagon. Give each vertex a color so that neighbours differ. Two colors fail, since the colors would have to alternate around an odd cycle. Three colors work. So the chromatic number, the fewest colors needed, is 3. Now merge the two ends of one edge into one vertex. The pentagon becomes a square. Merge again and it becomes a triangle, a complete graph on three vertices. A graph obtained by deleting and merging like this is a minor. The Hadwiger number h is the size of the largest complete graph you can reach. The pentagon has only five edges, and a complete graph on four vertices needs six. So h = 3, matching the 3 colors.

Hadwiger's conjecture, formulated in 1943, says the chromatic number never exceeds the Hadwiger number. Small cases were proved. The case of no five-vertex complete minor is equivalent to the Four-Color Theorem. Robertson, Seymour and Thomas proved the six-vertex case. For large graphs, the best general bounds had an extra slowly growing factor.

The first paper disproves the conjecture. It builds arbitrarily large graphs where every three vertices include at least one edge. In such a graph, one color can be used on at most two vertices. So a graph on m vertices needs at least m/2 colors. The paper shows h is less than 26m/75 + 2/3. Suppose a graph in the family has 1500 vertices. Then it needs at least 750 colors, but its largest complete minor has at most 520 vertices. The obstacle is to stop any large complete minor from forming. The graph is drawn at random, and some pairs are declared missing edges.

The third paper shows the conjecture is right up to a constant factor. There is one whole number C with chromatic number at most C times h, for every graph. This holds even when each vertex picks from its own list of colors. Such a C must be at least two. The second paper claims a similar counterexample to a conjecture of Colin de Verdière, which bounds coloring by a matrix invariant.

How sure is this? Lean, a computer proof checker, has formal statements of the first and third papers' main results. So those papers prove them, as far as the Lean statements match the papers. The Colin de Verdière result is outside the Lean scope, so it remains a claim. No specialist review of any of the papers is published.

What it doesn't show. This does not give an explicit small counterexample or a value for the constant factor; the constants are not optimized. The Colin de Verdière result and the fractional-coloring strengthening are outside the Lean scope.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Landmark if it holds up: it disproves a famous 1943 conjecture, and Lean has formal statements of the counterexample and the linear bound. The Colin de Verdière paper is a claim only. No specialist review is published.

Words used

Chromatic number
The fewest colors needed so that every edge joins two different colors.
Minor
A graph obtained from another by deleting vertices or edges and merging the two ends of edges.
Hadwiger number
The number of vertices of the largest complete graph that is a minor of a given graph.
Complete graph
A graph in which every two vertices are joined by an edge.
Independence number
The largest number of vertices with no edge between any two of them.
List coloring
Coloring where each vertex must take a color from its own given list.
Colin de Verdière invariant
A number attached to a graph from the eigenvalues of matrices that follow its edges.

The original papers (3)

Lean notes

All quoted lines (11)
  1. Hadwiger's conjecture, formulated in 1943, asserts that h(G)≥χ(G)h(G)\ge\chi(G) for every finite nonempty simple graph GG.
    A counterexample to Hadwiger's conjecture Back to text
  2. Wagner's structure theorem makes the four-colorability of graphs without a K5K_5 minor equivalent to the Four-Color Theorem, proved by Appel and Haken, with Koch contributing to the reducibility part.
    A counterexample to Hadwiger's conjecture Back to text
  3. Robertson, Seymour, and Thomas proved that every graph without a K6K_6 minor is five-colorable, by reducing the obstruction to a graph that becomes planar after one vertex is removed.
    A counterexample to Hadwiger's conjecture Back to text
  4. Delcourt and Postle reduced the bound to O(tlog⁡log⁡t)O(t\log\log t).
    A counterexample to Hadwiger's conjecture Back to text
  5. There are arbitrarily large integers mm for which an mm-vertex finite simple graph GG satisfies α(G)≤2and\cm(G)<m100.\alpha(G)\le2 \qquad\text{and}\qquad \cm(G)<\frac{m}{100}.
    A counterexample to Hadwiger's conjecture Back to text
  6. Thus Hadwiger's conjecture and its fractional-coloring weakening χf(G)≤h(G)\chi_f(G)\le h(G) are false.
    A counterexample to Hadwiger's conjecture Back to text
  7. We build GG by sampling from a finite probability space and declaring some pairs to be holes, or missing edges.
    A counterexample to Hadwiger's conjecture Back to text
  8. There is an absolute integer C≥1C\ge1 such that every finite nonempty simple graph GG satisfies ℓ(G)≤Ch(G).\ell(G)\le C h(G).
    A linear list-coloring bound in terms of the Hadwiger number Back to text
  9. This resolves the Linear List Hadwiger conjecture affirmatively.
    A linear list-coloring bound in terms of the Hadwiger number Back to text
  10. Thus a universal constant in Theorem … must be at least two.
    A linear list-coloring bound in terms of the Hadwiger number Back to text
  11. We disprove the Colin de Verdière chromatic conjecture by constructing graphs whose chromatic number exceeds their Colin de Verdière invariant by more than one.
    A counterexample to the Colin de Verdière chromatic conjecture Back to text

Other sources

  1. openai/math, Lean scope note for family 157 This disproves the ordinary chromatic form.
  2. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Combinatorics Graph theoryOpen since the 1940sLean-checked resultsLandmark results