Download Wolfram Notebook

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 ,

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

(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

(Zelinka 1976), of the complete k-partite graph is

for and (Ivančo 1988), and of the wheel complement graph is

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

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.

See also

Graph Minor, Hadwiger Conjecture, Hadwiger-Nelson Problem, Linear Hadwiger Conjecture

Explore with Wolfram|Alpha

References

Bollobás, B.; Catlin, P. A.; and Erdős, P. "Hadwiger's Conjecture Is True for Almost Every Graph." European J. Combin. 1, 195-199, 1980.Dallard, C.; Gollin, J. P.; and Munaro, A. "Treewidth Versus Hadwiger Number: Graph Classes with Dominated Balanced Separators Are Quasi-Linearly Treewidth-Hadwiger Bounded." 10 Nov 2026. https://arxiv.org/abs/2611.14070v1.Fowler, L.; and Li, G.; Pavelescu, A. "Complete Minors in Complements of Non-Separating Planar Graphs." 21 Apr 2022. https://arxiv.org/abs/2204.10134v1.Hadwiger, H. "Über eine klassifikation der Streckenkomplexe." Vierteljschr. Naturforsch. Ges. Zürich 88, No. 2, 133-142, 1943.Halin, R. "S-Functions for Graphs." J. Geometry 8, 171-186, 1976.Ivančo, J. "Some Results of the Hadwiger Numbers of Graphs." Math. Slovaca 38, 221-226, 1988.Kostochka, A. V. "On Hadwiger Numbers of a Graph and Its Complement." In Finite and Infinite Sets, Vol. I, II (Eger, 1981) (Ed. A. Hajnal, L. Lovász, and V. T. Sós). Amsterdam, Netherlands: North-Holland, pp. 537-545, 1984.Mel'nikov, L. S. "Recent Results of Novosibirsk Mathematicians in Graph Theory." Časopis Pest. Mat. 112, 89-96, 1987. https://doi.org/10.21136/CPM.1987.118297.Robertson, N.; Seymour, P. D.; and Thomas, R. "Linkless Embeddings of Graphs in 3-Space." Bull. Amer. Math. Soc. 28, 84-89, 1993.Stiebitz, M. "On Hadwiger Numbers of a Graph and Its Complement." In Contemporary Methods in Graph Theory. Mannheim, Germany: Bibliographisches Inst., pp. 557-568, 1990.Wood, D. R. "An Explicit Bound on the Extremal Function for Complete Graph Minors." 29 Oct 2026. https://arxiv.org/abs/2610.41060v1.Zelinka, B. "Hadwiger Number of Finite Graphs." Math. Slov. 26, 23-30, 1976.

Referenced on Wolfram|Alpha

Hadwiger Number

Cite this as:

Weisstein, Eric W. "Hadwiger Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HadwigerNumber.html

Subject classifications