Номер 203 — Алгебра 7 класс

В некотором городе с любой станции метро можно проехать на любую другую станцию (возможно, с пересадками). Докажите, что существует станция, которую можно закрыть (без права проезда через неё), и при этом с любой из оставшихся станций можно будет проехать на любую другую.

1. Рассмотрим самый длинный маршрут без повторения станций и его конечную станцию A. Все станции, соединённые с A, лежат на этом маршруте (иначе маршрут можно было бы продлить).
2. Закроем A. Любые две оставшиеся станции по-прежнему связаны: если путь между ними проходил через A, то его участок «сосед A — A — сосед A» можно заменить на участок маршрута между этими соседями, который не содержит A.