Hadwiger conjecture (graph theory)

Common card · No. 209222

In graph theory, the Hadwiger conjecture states that if G is loopless and has no Kt minor then its chromatic number satisfies χ(G)<t. It is known to be true for 1≤t≤6. The conjecture is a generalization of the four color theorem and is considered to be one of the most important and challenging open problems in the field. Reversing the implication, the conjecture can equivalently be stated in the following form. According to it, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph Kk on k vertices as a minor of G. The conjecture was made by Hugo Hadwiger in 1943. Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory". In October 2026, a bulk release by OpenAI included a claimed disproof...

Read on Wikipedia · Image David Eppstein, Public domain