Разделы 
Дополнительно
Задача по математике - 1978
2019-01-22 
В некотором государстве было 2002 города, соединенных дорогами так, что если запретить проезд через любой из городов, то из любого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.
Решение:
Построим граф, вершины которого соответствуют городам, а ребра - дорогам, существовавшим в стране до начала всех преобразований. По условию, над этим графом несколько раз подряд проделывается следующая операция: удаляются все ребра некоторого простого цикла, а все вершины этого цикла соединяются с новой вершиной. Докажем, что в графе, получившемся после окончания всех преобразований, все вершины исходного графа будут иметь степень 1. Поскольку таких вершин ровно 2002, это даст нам полное решение задачи.
Рассмотрим произвольную вершину $v$, принадлежащую исходному графу. По условию, при удалении этой вершины (и всех выходящих из нее ребер) из исходного графа образуется связный граф. Докажем, что это свойство сохраняется после применения к графу описанной в условии операции.
Рассмотрим произвольный граф $G$ и вершину и этого графа, при удалении которой образуется связный граф. Пусть после применения к графу $G$ описанной в условии операции образовался граф $G^{\prime}$. Рассмотрим произвольный путь в графе $G$, не проходящий через $u$. В графе $G^{\prime}$ некоторые ребра этого пути могут быть удалены, но их концы должны быть соединены с новой вершиной (обозначим ее $w$). Таким образом, заменив минимальный участок пути, содержащий все удаленные ребра, на пару ребер, соединяющих концы этого участка с вершиной $w$, мы получим путь в графе $G^{\prime}$, имеющий те же концы и не проходящий через $u$. Это означает, что если мы удалим из графа $G^{\prime}$ вершину и, то для любых двух вершин получившегося графа мы можем найти соединяющий их путь. Для старых (отличных от $w$) вершин этот путь получается описанным выше способом из пути, соединяющего их в графе, образовавшемся при удалении и из графа $G$, а вершина w должна быть соединена ребром хотя бы с одной из старых вершин, которая соединена путями со всеми остальными вершинами данного графа. Таким образом, при удалении вершины и из графа $G^{\prime}$ также образуется связный граф.
Из доказанного следует, что после всех преобразований при удалении из получившегося графа вершины $v$ образуется связный граф. Тогда, если степень вершины $v$ в получившемся графе больше 1, то между двумя соединенными с $v$ вершинами есть не проходящий через $v$ путь. Этот путь вместе с вершиной $v$ и двумя выходящими из нее ребрами образует в получившемся графе простой цикл, что по условию невозможно. Таким образом, степень вершины $v$ в этом графе равна 1.
В некотором государстве было 2002 города, соединенных дорогами так, что если запретить проезд через любой из городов, то из любого из оставшихся городов можно добраться до любого другого. Каждый год король выбирает некоторый несамопересекающийся циклический маршрут и приказывает построить новый город, соединить его дорогами со всеми городами выбранного маршрута, а все дороги этого маршрута закрыть за ненадобностью. Через несколько лет в стране не осталось ни одного несамопересекающегося циклического маршрута, проходящего по ее городам. Докажите, что в этот момент количество городов, из которых выходит ровно одна дорога, не меньше 2002.
Решение:
Построим граф, вершины которого соответствуют городам, а ребра - дорогам, существовавшим в стране до начала всех преобразований. По условию, над этим графом несколько раз подряд проделывается следующая операция: удаляются все ребра некоторого простого цикла, а все вершины этого цикла соединяются с новой вершиной. Докажем, что в графе, получившемся после окончания всех преобразований, все вершины исходного графа будут иметь степень 1. Поскольку таких вершин ровно 2002, это даст нам полное решение задачи.
Рассмотрим произвольную вершину $v$, принадлежащую исходному графу. По условию, при удалении этой вершины (и всех выходящих из нее ребер) из исходного графа образуется связный граф. Докажем, что это свойство сохраняется после применения к графу описанной в условии операции.
Рассмотрим произвольный граф $G$ и вершину и этого графа, при удалении которой образуется связный граф. Пусть после применения к графу $G$ описанной в условии операции образовался граф $G^{\prime}$. Рассмотрим произвольный путь в графе $G$, не проходящий через $u$. В графе $G^{\prime}$ некоторые ребра этого пути могут быть удалены, но их концы должны быть соединены с новой вершиной (обозначим ее $w$). Таким образом, заменив минимальный участок пути, содержащий все удаленные ребра, на пару ребер, соединяющих концы этого участка с вершиной $w$, мы получим путь в графе $G^{\prime}$, имеющий те же концы и не проходящий через $u$. Это означает, что если мы удалим из графа $G^{\prime}$ вершину и, то для любых двух вершин получившегося графа мы можем найти соединяющий их путь. Для старых (отличных от $w$) вершин этот путь получается описанным выше способом из пути, соединяющего их в графе, образовавшемся при удалении и из графа $G$, а вершина w должна быть соединена ребром хотя бы с одной из старых вершин, которая соединена путями со всеми остальными вершинами данного графа. Таким образом, при удалении вершины и из графа $G^{\prime}$ также образуется связный граф.
Из доказанного следует, что после всех преобразований при удалении из получившегося графа вершины $v$ образуется связный граф. Тогда, если степень вершины $v$ в получившемся графе больше 1, то между двумя соединенными с $v$ вершинами есть не проходящий через $v$ путь. Этот путь вместе с вершиной $v$ и двумя выходящими из нее ребрами образует в получившемся графе простой цикл, что по условию невозможно. Таким образом, степень вершины $v$ в этом графе равна 1.
