Hadwiger conjecture

Builds on Chromatic number Graph minor Complete graph

Statement

Let $k \ge 1$ be an integer, and let $G$ be a finite graph with chromatic number $\chi(G) \ge k$ . Then the complete graph $K_k$ is a minor of $G$ .

Remarks

Equivalently, every finite graph with no $K_k$ minor can be properly coloured with $k - 1$ colours. Hugo Hadwiger stated the conjecture in 1943. It is easy for $k \le 3$ , and Hadwiger proved it for $k = 4$ . For $k = 5$ it is equivalent to the four colour theorem, by a structure theorem of Wagner on graphs without a $K_5$ minor. For $k = 6$ Robertson, Seymour and Thomas proved it in 1993, by reduction to the four colour theorem. The conjecture is open for every $k \ge 7$ .

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Complete graph example
Graph colouring definition
Graph minor concept
K-colourable graph definition
Chromatic number definition
Hadwiger conjecture conjecture

Tag	`35NNSXJB1K`
URI	`m2://35NNSXJB1K`
Kind	conjecture
Writing	W0 stub
MSC	05C15, 05C83
Status	This copy of the site has no build data. Run `m2 status 35NNSXJB1K`.
About	Chromatic number, Graph minor
Uses	Chromatic number, Graph minor, Complete graph
Same as	Wikidata Q1128435 Wikipedia Hadwiger conjecture (graph theory)
Changed	2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.