Олимпиадная задача Карпова: цикл в графе с длиной, не делящейся на 3
Задача
В стране несколько городов, некоторые пары городов соединены дорогами. При этом из каждого города выходит хотя бы три дороги.
Докажите, что существует циклический маршрут, длина которого не делится на 3.
Решение
Предположим, что существует граф, степени всех вершин которого более двух, но длина каждого цикла в этом графе делится на 3. Рассмотрим такой граф G с наименьшим числом вершин.
Очевидно, в этом графе существует цикл Z, пусть этот цикл последовательно проходит по вершинам A1, A2, ..., A3k. Пусть существует путь S, соединяющий вершины Am и An и не проходящий по рёбрам цикла Z. Рассмотрим циклы Z1 и Z2, состоящие из пути S и двух половинок цикла Z. Поскольку длины обоих этих циклов кратны 3, то и длина пути S кратна 3. В частности, отсюда следует, что никакая вершина X, не входящая в цикл Z, не может быть соединена рёбрами с двумя разными вершинами цикла Z. Кроме того, рёбра, выходящие из вершин цикла Z, отличные от рёбер этого цикла, все различны.
Объединим все вершины A1, A2, ..., A3k цикла Z в одну вершину A, которую соединим рёбрами со всеми вершинами, которые были соединены с вершинами цикла Z. Очевидно, в полученном графе G1 меньше вершин, чем в графе G, и степень каждой вершины по-прежнему больше 2. Из доказанного выше следует, что длина любого цикла в графе G1 кратна 3. Противоречие с минимальностью графа G.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь