Гамільтонів граф

Нехай ${\displaystyle p}$ — число вершин в даному графі; якщо степінь кожної вершини не менший, ніж ${\displaystyle {\frac {p}{2}}}$, то граф називається графом Дірака. Граф Дірака — гамільтонів.

${\displaystyle p}$ — число вершин у даному графі. Якщо для будь-якої пари несуміжних вершин ${\displaystyle x}$, ${\displaystyle y}$ виконано нерівність ${\displaystyle d(x)+d(y)\geqslant p,}$ то граф називаваєтся графом Оре (словами: сума степенів будь-яких двох несуміжних вершин не менша від загального числа вершин у графі). Граф Оре — гамільтонів.

Теорема Бонді-Хватала узагальнює твердження Дірака і Оре. Спочатку визначимо замикання графу. Нехай у графу ${\displaystyle G\;}$ є ${\displaystyle p\;}$ вершин. Тоді замикання ${\displaystyle cl(G)\;}$ однозначно будується за G додаванням для всіх несуміжних вершин ${\displaystyle x\;}$ і ${\displaystyle y\;}$, у яких виконується ${\displaystyle d(x)+d(y)\geqslant p}$, нового ребра ${\displaystyle uv\;}$.

Граф є гамільтоновим тоді і тільки тоді, коли його замикання — гамільтонів граф.