Теория чисел на БИБНе

(a) Начертим граф возможных соседей. Рассмотрим три пары вершин в четырехугольниках на графе (они отмечены жирными точками), а именно: (2, 10), (1, 9) и (3, 11) — это вершины с наименьшей степенью (количеством соседей), равной 2.

Предположим, от противного, что есть простой путь на графе (т.е. без повторения вершин), проходящий через все вершины. Тогда найдется такая пара вершин среди трех указанных пар, что путь не начинается и не кончается в вершинах из этой пары (такая пара есть, т.к. концов у пути — два, а пар — три). Таким образом, обе вершины этой пары — “проходны”, но если впервые будет пройдена одна вершина из этой пары, то вторая вершина станет изолированной («отрезанной»: в неё нельзя будет попасть потом). Противоречие.

(b) Пример перестановки: 2, 5, 10, 7, 12, 9, 4, 1, 6, 3, 8, 11. Граф (см. рисунок) помогает построить подобный пример.