Простой путь, Гамильтонов путь, Гамильтонов цикл

Введем обозначения. Пусть — наибольшее количество вершин во всех возможных подграфах таких, что никакие две вершины не соединены ребром, — наименьшее количество вершин графа удаление которых приводит к потери связности

Так, исходная задача может быть переформулировано в следующем виде:

Пусть — граф, такой, что и Тогда — гамильтонов.

Перейдем к доказательству. Положим Предположим сначала, что в нет циклов. Поскольку и граф связный, а, значит, — это дерево. Т.к. то в есть хотя бы две несвязные висячие вершины, а, значит,

откуда в есть хотя бы один цикл. Пусть — самый длинный простой цикл в причем Удалим из все вершины, лежащие в и обозначим за любую связную компоненту в оставшемся графе. Определим Сразу ясно, что (действительно, связность могла нарушиться только из-за удаления ребер в Более того, не содержит для любого из множества (положим иначе в есть цикл, длиннее Все вышесказанное означает, что и а, значит, поскольку при удалении множество уже образует отдельную компоненту связности.

Определим — соседи всех из например, против часовой стрелки. Из рисунка выше следует, что пусто Заметим теперь, что независимое множество, иначе в опять-таки, есть цикл длиннее а, значит, откуда

Рассмотрим произвольную вершину и множество Поскольку то — тоже независимое множество, а, значит, — противоречие.