Разделы 
Дополнительно
Задача по математике - 1925
2019-01-22 
В стране несколько городов, некоторые пары городов соединены дорогами. При этом из каждого города выходит хотя бы 3 дороги. Докажите, что существует циклический маршрут, длина которого не делится на 3.
Решение:
Предположим, что существует граф, степени всех вершин которого более двух, но длина любого цикла в этом графе делится на 3. Рассмотрим такой граф $G$ с наименьшим числом вершин. Очевидно, в этом графе существует цикл $Z$, пусть этот цикл последовательно проходит по вершинам $A_1, A_2,\cdots, A_{3k}$. Пусть существует путь $S$, соединяющий вершины $A_m$ и $A_n$ и не проходящий по ребрам цикла $Z$. Рассмотрим циклы $Z_1$ и $Z_2$ , состоящие из пути $S$ и двух «половинок» цикла $Z$. Поскольку длины обоих этих циклов делятся на 3, нетрудно заметить, что длина пути $S$ делится на 3. В частности, из доказанного утверждения следует, что никакая вершина $X$, не входящая в цикл $Z$, не может быть соединена ребрами с двумя разными вершинами цикла $Z$. Кроме того, ребра, выходящие из вершин цикла $Z$, отличные от ребер этого цикла, все различны.
Объединим все вершины $A_1, A_2, \cdots, A_{3k}$ цикла $Z$ в одну вершину $A$, которую соединим ребрами со всеми вершинами, которые были соединены с вершинами цикла $Z$. Очевидно, в полученном графе $G_1$ меньше вершин, чем в графе $G$, и степень каждой вершины по-прежнему более двух. Из доказанного выше следует, что длина любого цикла в графе $G_1$ делится на 3. Мы получили противоречие: ведь в выбранном ранее графе $G$ было минимальное количество вершин среди всех таких графов.
Таким образом, в любом графе, степени всех вершин которого более двух, существует цикл, длина которого не делится на 3. Остается лишь применить это утверждение для графа, вершины которого соответствуют городам, а ребра - дорогам.
В стране несколько городов, некоторые пары городов соединены дорогами. При этом из каждого города выходит хотя бы 3 дороги. Докажите, что существует циклический маршрут, длина которого не делится на 3.
Решение:
Предположим, что существует граф, степени всех вершин которого более двух, но длина любого цикла в этом графе делится на 3. Рассмотрим такой граф $G$ с наименьшим числом вершин. Очевидно, в этом графе существует цикл $Z$, пусть этот цикл последовательно проходит по вершинам $A_1, A_2,\cdots, A_{3k}$. Пусть существует путь $S$, соединяющий вершины $A_m$ и $A_n$ и не проходящий по ребрам цикла $Z$. Рассмотрим циклы $Z_1$ и $Z_2$ , состоящие из пути $S$ и двух «половинок» цикла $Z$. Поскольку длины обоих этих циклов делятся на 3, нетрудно заметить, что длина пути $S$ делится на 3. В частности, из доказанного утверждения следует, что никакая вершина $X$, не входящая в цикл $Z$, не может быть соединена ребрами с двумя разными вершинами цикла $Z$. Кроме того, ребра, выходящие из вершин цикла $Z$, отличные от ребер этого цикла, все различны.
Объединим все вершины $A_1, A_2, \cdots, A_{3k}$ цикла $Z$ в одну вершину $A$, которую соединим ребрами со всеми вершинами, которые были соединены с вершинами цикла $Z$. Очевидно, в полученном графе $G_1$ меньше вершин, чем в графе $G$, и степень каждой вершины по-прежнему более двух. Из доказанного выше следует, что длина любого цикла в графе $G_1$ делится на 3. Мы получили противоречие: ведь в выбранном ранее графе $G$ было минимальное количество вершин среди всех таких графов.
Таким образом, в любом графе, степени всех вершин которого более двух, существует цикл, длина которого не делится на 3. Остается лишь применить это утверждение для графа, вершины которого соответствуют городам, а ребра - дорогам.
