Choose an arbitrary capital $A$. Say that a city $C$ is even (resp., odd) if the route from $A$ to $C$ contains an even (resp., odd) number of flights. It suffices to prove that the sum of mayors' numbers in odd cities is equal to the sum of those in even cities. This claim can be proved by means of a bijection of the corresponding sets of enumerations; this bijection merely swaps $1$ and $2$.

Назовём какой-нибудь город $A$ столицей. Назовём город чётным, если маршрут из $A$ до него содержит чётное число рейсов, и нечётным иначе. Тогда чётность любых двух городов, соединённых рейсом, различна. Мы докажем, что сумма чисел, полученных мэрами чётных городов, равна сумме чисел, полученных мэрами нечётных; из этого следует утверждение задачи.

Назовём нумерацию городов подходящей для города $X$, если мэр города $X$ её посчитал. Ясно, что в любой нумерации, подходящей городу $X$, он имеет номер $1$, так что каждая нумерация подходит не более, чем одному городу.

Рассмотрим любую нумерацию, подходящую чётному городу $E$. Пусть номер $2$ в ней носит город $W$; тогда $W$ — нечётный город, соединённый с $E$, иначе на маршруте от $E$ до $W$ встретился бы город с большим номером. Поменяем местами номера $1$ и $2$; мы получим нумерацию, в которой номер $1$ носит нечётный город $W$.

Рассмотрим любой маршрут $m$, начинающийся в $W$. Он получается из некоторого маршрута, выходящего из $E$, либо добавлением города $W$ в начало (если $m$ проходит через $E$), либо откидыванием $E$ из начала (в противном случае). Тогда легко видеть, что после обмена $1$ и $2$ номера на $m$ идут в порядке возрастания.

Итак, после перемены номеров $1$ и $2$ из нумерации, подходящей для чётного города, получается нумерация, подходящая для нечётного (и наоборот). Это сопоставление взаимно однозначно. Значит, тех и других нумераций поровну, что и требовалось доказать.