Hadwiger conjecture

Summary

AI-assisted claims

Claims as their sources state them. Papex has not checked them; the status stays the source’s.

Why it is open

A graph is a set of vertices joined by edges. Its chromatic number is the fewest colours that give joined vertices different colours, and its Hadwiger number is the size of its largest complete minor, the largest set of vertices, all joined to each other, that deleting and contracting can produce [6]. Hugo Hadwiger conjectured in 1943 that the chromatic number never exceeds the Hadwiger number, and noted that this would settle the four colour problem [1]. Paul Seymour calls it "probably the most famous open problem in graph theory" [6]. It is a different problem from the Hadwiger–Nelson problem on colouring the plane.

The conjecture is one statement for each number of colours k. It is proved for k ≤ 6 and open from k = 7 on [6, 12]. For graphs with no minor on seven mutually joined vertices (no K7 minor), it is not even known that seven colours suffice; the best proved bound is eight [10]. A resolution is either a proof for every k or a single graph whose chromatic number exceeds its Hadwiger number [6]. A counterexample built from large graphs, such as the one claimed in 2026 (see below), would leave the small cases open, starting with whether graphs without a K7 minor can be coloured with six colours [10, 13].

Seymour gives one reason the problem resists proof: "graphs can have large chromatic number for obscure reasons" [6]. Even where the reason is plain it is hard: he notes that the only known proof that every planar graph on n vertices has n/4 vertices with no two joined goes through the four colour theorem [6]. He calls graphs in which no three vertices are pairwise unjoined "an excellent place to look for a counterexample" [6].

What is known

Small cases (1943–1993). Hadwiger proved the cases k ≤ 4 when he stated the conjecture, in a lecture of December 1942 printed in 1943 [1, 6]. In 1937 Klaus Wagner showed that the case k = 5 is equivalent to the four colour theorem, so it became a theorem when that was proved in 1976 [6]. In 1993 Neil Robertson, Seymour and Robin Thomas proved k = 6 by showing that a minimal counterexample would be a planar graph plus one vertex, which the four colour theorem then colours with five colours [4, 6].

Bounds for large k (1984–2026). A graph without a K_k minor has few edges, so it has a vertex of small degree, and colouring vertex by vertex gives a bound [6]. In 1984 Alexandr Kostochka and Andrew Thomason independently showed that such graphs have average degree of order k√(log k), so O(k√(log k)) colours suffice, and this degree bound cannot be improved [2, 3, 6, 9]. Sergey Norin, Luke Postle and Zi-Xia Song broke the resulting barrier in 2023 with O(k(log k)^β) colours for every β > 1/4 [7]. Michelle Delcourt and Postle reached O(k log log k) and showed that a bound of the form C·k, the "linear Hadwiger conjecture", reduces to graphs with few vertices [8]. In a September 2026 preprint, Chun-Hung Liu and Jason Luo report O(k log log log k); they state that "ChatGPT Codex was used to help develop the proof" [9].

Relaxations and variants. In a fractional colouring, sets of pairwise unjoined vertices receive weights that add up to at least 1 at every vertex. Bruce Reed and Seymour proved in 1998 that graphs with no K_(p+1) minor have fractional chromatic number at most 2p, twice the bound the conjecture predicts [5]. Stronger versions have fared worse: the list-colouring version fails already for k = 5 [6], and a December 2025 preprint by Marcus Kühn, Lisa Sauermann, Raphael Steiner and Yuval Wigderson gives a counterexample to the "odd" Hadwiger conjecture, proposed in 1993 [11].

Independence number two. If no three vertices are pairwise unjoined, each colour can be used at most twice, so a graph on n vertices needs at least n/2 colours and the conjecture predicts a complete minor on about n/2 vertices [6]. A theorem of Pierre Duchet and Henri Meyniel gives n/3; when Seymour wrote his survey, it was open whether any fixed fraction above 1/3 is always reached [6].

The first open case. In a September 2026 preprint, Zdeněk Dvořák, Norin and Neil Rahman prove that graphs with no minor of K7 minus two disjoint edges are 6-colourable. They describe the contribution of AI to the proofs as "analogous to what could be expected from a strong Master's student" [10].

Recent claims. On 4 October 2026 Norin and Steiner posted a preprint claiming the linear Hadwiger conjecture: some constant C makes every graph without a K_t minor colourable with Ct colours [12]. Its abstract states: "The proof was found by GPT-6 Astra, following the directions by the authors." The authors wrote the paper, take responsibility for its correctness and link a Lean formalisation "produced by OpenAI Codex" [12].

On 6 October 2026 OpenAI released "A counterexample to Hadwiger's conjecture", dated 23 September 2026, in its openai/math repository of manuscripts "produced by an internal OpenAI model" [13]. It claims arbitrarily large graphs with no three pairwise unjoined vertices whose chromatic number, and even fractional chromatic number, exceeds their Hadwiger number: on m vertices, the Hadwiger number is below 26m/75 + 2/3 while at least m/2 colours are needed [13]. The repository says its results are "at different stages of verification". A Lean formalisation of the ordinary-colouring statement was added on 7 October, the formal proofs' review status is listed as "unchecked", and no revision or withdrawal of the manuscript was recorded by 14 October [13]. Gil Kalai wrote on his blog: "The new announcement gives counterexamples to the original conjecture, even among graphs with independence number at most two." He added that the collection's "proofs will need to be checked and digested by the mathematical community" [14]. The same release claims a linear bound for list colouring; Yangyan Gu and Rongxing Xu write that "OpenAI provided a proof of the conjecture" and give a shorter proof building on it [15].

Main approaches

Reduction to the four colour theorem. Show that a smallest counterexample must have a special structure, such as a planar graph plus one vertex, and then use the four colour theorem [4, 6]. Strongest evidence: the cases k = 5 and k = 6 [6], and the 2026 result for K7 minus two disjoint edges [10]. Main difficulty: Dvořák, Norin and Rahman show that the edge-counting statement their method needs is false for graphs without a K7 minor, which makes "the final step" to K7 "substantially more difficult" [10].

Degree and density bounds. Bound the number of edges in graphs without a large complete minor, then colour [3, 6]. Strongest evidence: the sequence from O(k√(log k)) to O(k log log log k) [2, 3, 7, 8, 9]. Main difficulty: degree arguments alone cannot beat k√(log k) [6, 9], and even a linear bound C·k would not give the exact conjecture.

Fractional colouring. Prove bounds for weighted colourings first, where linear programming gives extra tools [5, 6]. Strongest evidence: the 2p bound [5], which the 2026 linear-bound preprint lists among its ingredients [12]. Main difficulty: the proved bound is twice the conjectured one [5], and the OpenAI manuscript claims that even the fractional version of the conjecture fails [13].

Graphs with independence number two. Test the conjecture where many colours are needed for a plain reason [6]. Strongest evidence: complete minors of order n/3 [6]. Main difficulty: no fixed fraction above 1/3 was known when Seymour wrote [6]; this is also where the 2026 counterexample is claimed [13].

Open sub-questions

1. K7. Is every graph without a K7 minor 6-colourable, or at least 7-colourable? The best proved bound is eight [6, 10].
2. K7 minus an edge. Does every 5-connected graph with n ≥ 6 vertices and at least 4n − 2 edges contain K7 minus one edge as a minor? Dvořák, Norin and Rahman show this would make graphs without that minor 6-colourable [10].
3. Independence number two. Is there a fixed c > 1/3 such that every graph on n vertices with no three pairwise unjoined vertices has a complete minor on cn vertices [6]? The claimed counterexamples have Hadwiger number below 26n/75 + 2/3 [13].
4. How large is the gap? If the claimed examples stand, how large can chromatic number divided by Hadwiger number become? The claim gives at least m/2 colours against a Hadwiger number below 26m/75 + 2/3 [13], and the linear-bound preprint caps the ratio by a constant [12].
5. Smallest failure. If the conjecture fails, what is the smallest k at which it fails? It holds for k ≤ 6 [6], and the claimed construction is stated for sufficiently large parameters [13].

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

1. Hadwiger, H. (1943). Über eine Klassifikation der Streckenkomplexe. Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 88, 133–142 (lecture of 15 December 1942). Source · Checked 14 Oct 2026
2. Kostochka, A. V. (1984). Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica 4(4), 307–316. 10.1007/BF02579141 · Checked 14 Oct 2026
3. Thomason, A. (1984). An extremal function for contractions of graphs. Mathematical Proceedings of the Cambridge Philosophical Society 95(2), 261–265. 10.1017/S0305004100061521 · Checked 14 Oct 2026
4. Robertson, N., Seymour, P. & Thomas, R. (1993). Hadwiger's conjecture for K6-free graphs. Combinatorica 13(3), 279–361. 10.1007/BF01202354 · Checked 14 Oct 2026
5. Reed, B. & Seymour, P. (1998). Fractional colouring and Hadwiger's conjecture. Journal of Combinatorial Theory, Series B 74(2), 147–152. 10.1006/jctb.1998.1835 · Checked 14 Oct 2026
6. Seymour, P. (2016). Hadwiger's conjecture. In Open Problems in Mathematics, Springer, 417–437. 10.1007/978-3-319-32162-2_13 · Checked 14 Oct 2026
7. Norin, S., Postle, L. & Song, Z.-X. (2023). Breaking the degeneracy barrier for coloring graphs with no K_t minor. Advances in Mathematics 422, 109020. 10.1016/j.aim.2023.109020 · Checked 14 Oct 2026
8. Delcourt, M. & Postle, L. (2025). Reducing linear Hadwiger's conjecture to coloring small graphs. Journal of the American Mathematical Society 38(2), 481–507 (published online 2024). 10.1090/jams/1047 · Checked 14 Oct 2026
9. Liu, C.-H. & Luo, J. (2026). Beyond halfway to Hadwiger's conjecture. arXiv:2609.06867v2 (preprint, not peer reviewed; v1 6 September, v2 9 September 2026). Source · Checked 14 Oct 2026
10. Dvořák, Z., Norin, S. & Rahman, N. (2026). Every graph with no K7= minor is 6-colorable. arXiv:2609.17760v1 (preprint, not peer reviewed; 15 September 2026). Source · Checked 14 Oct 2026
11. Kühn, M., Sauermann, L., Steiner, R. & Wigderson, Y. (2025). Disproof of the odd Hadwiger conjecture. arXiv:2512.20392v1 (preprint, not peer reviewed; 23 December 2025). Source · Checked 14 Oct 2026
12. Norin, S. & Steiner, R. (2026). A proof of the linear Hadwiger conjecture. arXiv:2610.05291v1 (preprint, not peer reviewed; 4 October 2026). Source · Checked 14 Oct 2026
13. OpenAI (2026). A counterexample to Hadwiger's conjecture. Manuscript dated 23 September 2026, released 6 October 2026 in the openai/math repository, family 157 ("Graph coloring, clique minors, and Colin de Verdière invariants"). Source · Checked 14 Oct 2026
14. Kalai, G. (2026, 7 October). Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans. Combinatorics and more (blog). Source · Checked 14 Oct 2026
15. Gu, Y. & Xu, R. (2026). A shorter proof of the linear list Hadwiger conjecture. arXiv:2610.01946v2 (preprint, not peer reviewed; v1 of 1 October 2026 had the title "Improved upper bounds on the list chromatic number of K_t-minor-free graphs"; v2 of 12 October 2026). Source · Checked 14 Oct 2026

Page reviewed 14 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.