In autumn 2026, two remarkable results changed our understanding of one of the most famous conjectures in graph theory, formulated by Hugo Hadwiger in 1943. On the one hand, Norin and Steiner (Norin and Steiner 2026) proved that a certain weaker version of Hadwiger’s conjecture is true. On the other hand, a preprint of OpenAI (OpenAI 2026) announced counterexamples to the original conjecture, which had resisted the efforts of mathematicians for more than eighty years.
The two results complement each other beautifully: although Hadwiger’s conjecture is false, it is true up to a constant factor.
Let us recall the problem.
A graph consists of a set of vertices, some pairs of which are joined by edges. A proper colouring of a graph assigns colours to its vertices so that every two vertices joined by an edge have different colours.
The smallest number of colours needed for a proper colouring of a graph is called its chromatic number, denoted by .
Let denote the complete graph with vertices, in which every pair of distinct vertices is joined by an edge. Clearly,
Given an edge of a graph, we can contract it by merging its two endpoints into a single vertex, which is joined to all their former neighbours. A graph is called a minor of if it can be obtained from by repeatedly deleting edges or vertices and contracting edges.
For example, a cycle of length four does not contain a triangle as a subgraph, but contracting any one of its edges produces a triangle. Thus, is a minor of the four-cycle.
The Hadwiger number is the largest integer such that contains as a minor. Equivalently, is the largest number of disjoint connected groups of vertices that can be chosen so that every two groups are joined by at least one edge.
In 1943, Hadwiger (Hadwiger 1943) conjectured that for every finite graph .
In other words, he predicted that if a graph cannot be coloured with fewer than colours, then it must contain a minor.
This conjecture is a far-reaching generalization of the famous Four Colour Theorem. Indeed, the case is equivalent to the assertion that every planar graph can be coloured with four colours. A graph is called planar if it can be drawn in the plane without crossing edges. We discussed a recent algorithmic improvement related to the Four Colour Theorem in an earlier post.
Hadwiger’s conjecture was proved for , but the general problem remained open.
An important partial result was obtained independently by Kostochka and Thomason in the 1980s. They showed that every graph without a minor can be coloured with colours, where denotes the natural logarithm and means at most a constant multiple of .
For decades, this bound resisted substantial improvement. In 2023, Norin, Postle, and Song (Norin et al. 2023) improved it to for every fixed . Then Delcourt and Postle (Delcourt and Postle 2025) obtained the stronger bound in 2025.
However, the ultimate goal was to remove the logarithmic factor completely and establish a bound linear in . This became known as the Linear Hadwiger Conjecture.
In October 2026, Sergey Norin and Raphael Steiner (Norin and Steiner 2026) announced its proof.
The theorem is a major breakthrough because the factor is independent of the graph and of . Thus, the chromatic number of any graph is bounded by a universal constant times the order of its largest complete minor.
The proof builds on an important result of Delcourt and Postle (Delcourt and Postle 2025), who showed that proving the linear bound could be reduced to studying graphs whose number of vertices is not too large compared with .
Norin and Steiner first establish the required colouring bound for sufficiently small graphs. They then develop a method for extending it to larger graphs by repeatedly improving the range in which the bound applies. Combining this argument with the reduction of Delcourt and Postle gives the general theorem.
Norin and Steiner explicitly acknowledge that the proof was developed by GPT-6 Astra, following research directions and feedback supplied by the authors.
The constant arising from the original proof is enormous, of order . However, in a subsequent paper, David Wood (Wood 2026) used AI-assisted optimization to reduce it to
One might hope that further improvements would eventually give , thus proving Hadwiger’s original conjecture.
But another 2026 result shows that this is impossible.
In September 2026, OpenAI posted a preprint (OpenAI 2026) announcing the construction of graphs whose chromatic number is strictly larger than their Hadwiger number. In fact, the construction gives a stronger quantitative conclusion.
Taking , we obtain which directly contradicts Hadwiger’s conjecture.
The additional property concerning three vertices is particularly surprising. A set of vertices is called independent if no two of them are joined by an edge. Thus, the theorem asserts that the counterexamples can be constructed without independent sets of size three.
Why is this useful?
Suppose that has vertices and no independent set of size three. In any proper colouring, the vertices of each colour form an independent set. Consequently, each colour can be assigned to at most two vertices, giving
The OpenAI preprint constructs arbitrarily large graphs of this type for which Thus, for sufficiently large , the ratio is at least approximately This explains the constant in the theorem.
Let us briefly discuss the construction. The authors start with a large collection of vertices and carefully choose which pairs are not joined by an edge. These missing edges are arranged so that no three of them form a triangle. This ensures that the resulting graph has no independent set of size three.
At the same time, the authors use a sophisticated probabilistic construction to prevent the graph from containing very large complete minors. The central difficulty is that a minor may be obtained by contracting many edges, so merely controlling complete subgraphs is not sufficient. The proof instead controls collections of disjoint edges that are interconnected in a way that would help produce large complete minors.
The resulting graphs have extremely large chromatic number relative to the order of their largest complete minor.
The main counterexample has also been formalized in the Lean proof assistant, providing additional evidence for the correctness of the construction.
Combining the two theorems gives a particularly striking conclusion. If denotes the smallest constant for which holds for every finite graph , then the results imply
Thus, the existence of a universal constant has been established, but its optimal value is far from known.
The original Hadwiger conjecture, predicting , is false. Nevertheless, the Linear Hadwiger Conjecture is true, showing that the original prediction captured a genuine and powerful relationship between graph colouring and graph minors.
Both works are currently available as preprints, and their proofs merit careful independent scrutiny. Taken together, they represent an extraordinary development in graph theory: one of its oldest conjectures has been disproved, while a weaker version that preserves its central quantitative insight has finally been proved.