Условие
В графе 20 вершин, степень каждой не меньше 10. Доказать, что в нём есть гамильтонов путь.
Решение
Выберем самый длинный путь L, в котором вершины не повторяются. Предположим, что он содержит n < 20 вершин. Тогда вне пути лежат 20 – n вершин. Рассмотрим конечную точку K этого пути. Если хотя бы одно ребро ведёт из K в наружную (не принадлежащую L) вершину, то путь L можно удлинить, что противоречит его выбору.
Пусть все пути из K ведут в вершины пути L. Тогда этих вершин не меньше 10 (значит, n > 10). Для каждой такой вершины A рассмотрим вершину A', следующую за ней на пути L. Если хотя бы одно ребро ведёт из A' в (фиксированную) наружную вершину B, то пройдём по пути L от начала до точки A, затем по ребру AK, вернёмся по пути L в точку A' и, наконец, пройдём по ребру A'B. В результате получится путь, содержащий все вершины L и точку B. Снова противоречие.
Значит, с B соединены не более n – 10 вершин пути L. Но тогда степень B не больше (n – 10) + (19 – n) = 9. Противоречие.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Иванов С.В. |
|
Название |
Математический кружок |
|
глава |
|
Номер |
5 |
|
Название |
Графы |
|
Тема |
Теория графов |
|
задача |
|
Номер |
23 |
