The Hadwiger number of a graph 
, variously denoted 
(Zelinka 1976, Ivančo 1988) or 
(Stiebitz 1990), is the number of vertices
in the largest complete minor
of 
(Hadwiger 1943, Fowler et al. 2022). The Hadwiger number is also called the
contraction clique number (Bollobás et al. 1980) or homomorphism degree
(Halin 1976).
The Hadwiger conjecture states that for any loopless graph 
,
 |
(1)
|
where 
is the chromatic number of 
(Hadwiger 1943).
Forests have 
, graphs
with treewidth at most 2 have 
, planar graphs
have 
, and apex graphs
have 
.
The graphs with Hadwiger number at most five include the apex graphs and the linklessly
embeddable graphs (Robertson et al. 1993), both of which have the complete
graph 
among their forbidden minors.
Computing the Hadwiger number of a graph is an NP-hard problem.
For a finite simple graph 
with vertex
count 
and its graph complement 
, the Hadwiger number satisfies
 |
(2)
|
(Kostochka 1984; Mel'nikov 1987, p. 92; Stiebitz 1990).
The Hadwiger number of a finite simple connected graph with vertex cuts is equal to the maximum of the Hadwiger numbers of its blocks, and the Hadwiger number of a finite simple disconnected graph is equal to the maximum of the Hadwiger numbers of its connected components (Zelinka 1976).
The Hadwiger number of the complete bipartite graph 
is
 |
(3)
|
(Zelinka 1976), of the complete k-partite graph 
is
 |
(4)
|
for 
and 
(Ivančo 1988), and of the wheel complement
graph 
is
 |
(5)
|
for 
, where 
is the floor function
(Fowler et al. 2022).
For a finite simple graph 
with 
vertices and 
edges, Wood (2026, Theorem 1)
proves 
for every integer 
satisfying
 |
(6)
|
This gives a lower bound from the edge count and vertex count. Failure of the condition
for a particular 
does not rule out a complete graph minor 
. Wood (2026) reports checking the proof
at a high level while relying on Claude-developed numeric scripts and a Lean formalization
for technical and numerical details.
The Hadwiger number also controls treewidth in some families of finite graphs
closed under taking induced subgraphs. Dallard
et al. (2026) proved that graphs with no induced
cycle of even length have treewidth 
. More generally, let such a family
have fixed constants 
and 
such that every binary weighting of the vertices
admits a set 
of at most 
vertices whose closed graph
neighborhood can be deleted leaving every connected
component with at most 
times the total weight. Then its graphs
have treewidth 
(Dallard et al. 2026). These are class-dependent
asymptotic bounds, not formulas for the exact Hadwiger number. The authors credit
ChatGPT with the geometric-separation connection and an initial proof
of their key minor bound.
