Применим индукцию по $N$. Утверждение задачи очевидно при $N=1$ и $N=2$. Пусть $\Gamma_1$ — множество городов, из которых исходит одна дорога, а $\Gamma$ — множество остальных городов. Начав движение по различным дорогам из некоторого города, согласно условию, мы не сможем попасть дважды в один и тот же город, поэтому когда-нибудь мы закончим движение в городе из множества $\Gamma_1$. Это означает, что множество $\Gamma_1$ непусто. Ясно, что при $N \ge 3$ множество $\Gamma$ непусто, и в нем меньше, чем $N$ городов.

Назовем значимостью мэра количество городов, соседних с городом, где он работает. По условию значимость каждого мэра после реформы не уменьшилась. В частности, мэр города, принадлежащего множеству $\Gamma$, после реформы стал мэром некоторого города из множества $\Gamma$, то есть в результате реформы в городах множества $\Gamma$ тоже произошла перестановка мэров. Ясно, что из любого города $A \in \Gamma$ можно доехать до любого другого города $B \in \Gamma$, не заезжая в города множества $\Gamma_1$.

Поэтому множество городов $\Gamma$ и реформа, рассмотренная только на городах из $\Gamma$, удовлетворяет условию задачи. Применив предположение индукции, получаем, что в множестве $\Gamma$ либо найдется город, в котором мэр после реформы не поменялся, либо найдется пара соседних городов, обменявшихся мэрами, что и требовалось.