Докажем наше утверждение индукцией по числу площадей. Если площадей две, то оставим две улицы, соединяющие первую площадь со второй и вторую с первой, а остальные закроем.
Пусть площадей больше двух. Предположим, что нам удалось указать замкнутый маршрут по улицам города, начинающийся и кончающийся на площади $A$ и проходящий не менее чем по трём площадям. (Как строятся кольцевые маршруты, показано на рисунке 2: мы берём маршрут, соединяющий площадь $A$ с некоторой площадью $B$, затем маршрут, соединяющий $B$ с $A$, и выделяем нужный нам маршрут — красное «кольцо» на рисунке.) Изменим план города: объявим весь этот кольцевой маршрут новой площадью, а улицами объявим все улицы, не входящие в наш кольцевой маршрут, сохранив на них направление движения. При этом у нас, возможно, появятся улицы, начинающиеся и кончающиеся на новой площади. Проверим, что полученный «город» удовлетворяет всем условиям задачи. Для этого нужно убедиться, что на новую площадь выходит не меньше трёх улиц. Это обеспечивается нашим предположением, что в кольцевом маршруте не меньше трёх площадей (см. рис. 3). Не менее ясно, что по-прежнему с любой площади можно проехать на любую другую, — наша «перепланировка» могла только сократить соответствующие маршруты. Таким образом, мы получили город, удовлетворяющий условиям задачи и имеющий меньшее число площадей. По предположению индукции в нём есть «лишняя» улица. Ей соответствует некоторая улица старого города. Запретим по ней движение. Легко убедиться, что проезд по-прежнему возможен. Действительно, рассмотрим площади $\textit{П}_1$ и $\textit{П}_2$ и маршрут, соединяющий $\textit{П}_1$ с $\textit{П}_2$ в новом городе и не проходящий через закрытую улицу. Перенесём этот маршрут в старый город. Если этот маршрут не проходил через новую площадь, то он соединяет $\textit{П}_1$ с $\textit{П}_2$. В противном случае он разобьётся на две части: до «кольца» и после «кольца». Добавив к нему соответствующую часть кольца, мы получим нужный маршрут, соединяющий $\textit{П}_1$ с $\textit{П}_2$, в старом городе и не проходящий через закрытую улицу.
Осталось рассмотреть города, в которых нет длинных кольцевых маршрутов. Возьмём некоторую площадь $A$ такого города. Если с неё можно проехать на площадь $B$ по одной улице, то и с площади $B$ на неё можно проехать по одной улице — иначе удалось бы указать большое кольцо. Поступим теперь следующим образом: рассмотрим площадь $A$ и соседнюю с ней площадь $B_1$. Площадь $B_1$ соединена с площадью $A$ (см. рис. 4). Кроме этого, есть ещё одна улица, выходящая на $A$. Пусть она другим концом выходит на площадь $B_2$. Но тогда есть ещё одна улица, соединяющая $A$ и $B_2$ — с противоположным направлением движения. Поэтому если мы объявим кольцо $AB_1A$ новой площадью, условия задачи будут выполнены: на новую площадь будет выходить не меньше трёх улиц.
