Гамильтонов Цикл

[kot_matroskin]

Задача: Любой ли шестивершинный граф с минимальной степеньювершин не менее трех Гамильтонов? Пока мыслей нет. Подскажите пожалуйста хотя быя в каком направлении думать.

[Zealint]

Вам нужно узнать, что такое граф Дирака и всё станет понятно.

[kot_matroskin]

Если я правильно понял - ответ очевиден - любой такой граф удовлетворяет условию Дирака. Т.к. степень каждой вершины не меньше трёх. а вершин 6. Вот так как-то. Или я не прав?

[Mitrius_Math]

kot_matroskin, могу порекомендовать книгу "Элементы теории графов" Домнина Л.Н. Там есть что-то про гамильтоновы циклы.

[Zealint]

kot_matroskin в сообщении #613499 писал(а):

Или я не прав?

Всё верно.