# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

In graph theory, the Hadwiger conjecture (or "Hadwiger's conjecture") states that, if the complete graph on k vertices, Kk, is not a minor of a graph G, then G has a vertex coloring with k - 1 colors. Equivalently, if there is no sequence of edge contractions (each identifying the two endpoints of an edge) that brings graph G to the complete graph Kk, then G has a vertex coloring with k - 1 colors.

This conjecture was made by Hugo Hadwiger in 1943. In the same paper, Hadwiger proved the conjecture for $k \leq 4$. Wagner proved in 1937 that the case k = 5 is equivalent to the four color theorem and therefore we now know it to be true. (Note that the case k = 5 easily implies the four color theorem because K5 is not a minor of any planar graph.) Robertson, Seymour, and Thomas (1993) proved Hadwiger's conjecture for k = 6, also using the four color theorem. Thus the conjecture is true for $k \leq 6$ but it remains unsolved for all k > 6.

Some sources define the Hadwiger number h(G) of a graph G to be the size k of the largest complete graph Kk that is a minor of G (or equivalently can be obtained by contracting G). Then the Hadwiger conjecture can be stated in the simple algebraic form $\chi(G) \leq h(G)$ where χ(G) denotes the chromatic number of G.