Гамильтонов ли следующий граф? (Если да, то найдите в нём гамильтонов цикл; если нет — докажите.)

Посмотрим на вершины, отмеченные синим цветом.

Видно, что их 6 штук, и они попарно не соединены друг с другом.

Предположим, что гамильтонов цикл существует.

Заметим, что тогда в нем найдутся две подряд идущие ...