Гіпотеза Хадвігера

У графі, пофарбованому в 4 кольори, відзначені 4 підграфи, між будь-якими двома з них є ребро

Гіпотезу Хадвігера можна сформулювати інакше: у кожному ${\displaystyle k}$-хроматичному графі обов'язково існує ${\displaystyle k}$ зв'язних підграфів, які не перетинаються і між будь-якими двома з них є ребро.

Якщо ввести для графу число Хадвігера ${\displaystyle h(G)}$ — максимальне ${\displaystyle k}$ таке, що ${\displaystyle G}$ стягується до повного графу на ${\displaystyle k}$ вершинах, то гіпотеза формулюється у вигляді нерівності ${\displaystyle \chi (G)\leqslant h(G)}$, де ${\displaystyle \chi (G)}$ — хроматичне число графу.