Ця стаття не містить посилань на джерела. Ви можете допомогти поліпшити цю статтю, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (липень 2024)

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

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

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