---
tag: B4V4WAYVAW
kind: concept
name: Hadwiger number
aliases: [contraction-clique-number]
sources:
  - wikipedia: en:1665366@r1346157100
    locator: Hadwiger number
    note: adopted
    mention: wikipedia://en/1665366
    sections: [Summary]
same_as:
  wikidata: Q5638117
  wikipedia: Hadwiger number
inventory: [R04C181XXQ]
---

## Summary

In graph theory, the **Hadwiger number** of an undirected graph $G$ is the size of the largest [[complete graph|03WKB2H474]] that can be obtained by contracting edges of $G$. Equivalently, the Hadwiger number $h(G)$ is the largest number $n$ for which the complete graph $K_{n}$ is a minor of $G$, a smaller graph obtained from $G$ by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the **contraction clique number** of $G$ or the **homomorphism degree** of $G$. It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of $G$.