In graph theory, the Hadwiger number of an undirected graph is the size of the largest complete graph that can be obtained by contracting edges of . Equivalently, the Hadwiger number is the largest number for which the complete graph is a minor of , a smaller graph obtained from by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of or the homomorphism degree of . 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 . The graphs that have Hadwiger number at most four have been characterized by . The graphs with any finite bound on the Hadwiger number are sparse, and have small chromatic number. Determining the Hadwiger number of a graph is NP-hard but fixed-parameter tractable. Graphs with small Hadwiger number A graph has Hadwiger number at most two if and only if it is a forest, for a three-vertex complete minor can only be formed by contracting a cycle in . A graph has Hadwiger number at most three if and only if its treewidth is at most two, which is true if and only if each of its biconnected components is a series–parallel graph. Wagner's theorem, which characterizes the planar graphs by their forbidden minors, implies that the planar graphs have Hadwiger number at most four. In the same paper that proved this theorem, also characterized the graphs with Hadwiger number at most four more precisely: they are graphs that can be formed by clique-sum operations that combine planar graphs with the eight-vertex Wagner graph. The graphs with Hadwiger number at most five include the apex graphs and the linklessly embeddable graphs, both of which have the complete graph among their forbidden minors. Sparsity Every graph with vertices and Hadwiger number has edges. This bound is tight: for every , there exist graphs with Hadwiger number that have edges. If a graph has Hadwiger number , then all of its subgraphs also have Hadwiger number at most , and it follows that must have degeneracy . Therefore, the graphs with bounded Hadwiger number are sparse graphs. Coloring The Hadwiger conjecture states that the Hadwiger number is always at least as large as the chromatic number of . That is, every