Каждый город соединен с любым другим дорогой с одн...

Рассмотрим ориентированный граф, где вершины — города, а между любыми двумя городами есть ровно одна дорога в одну из сторон. Такой граф называется турниром.

Докажем, что в нем найдется город, из которого до любого другого можно добраться не более чем за 2 переезда.

Выберем город $A$, из которого выходит максимальное число дорог.

Теперь возьмем любой другой город $B$.

Если есть дорога $A \to B$, то из $A$ в $B$ можно доехать напрямую.

Остается случай, когда дороги $A \to B$ нет. Тогда, поскольку между любыми двумя городами есть ровно одна односторонняя дорога, обязательно есть дорога

$$B \to A.$$

Обозначим через $S$ множество городов, в которые можно попасть из $A$ напрямую. Тогда

$$|S| = d^+(A),$$

где $d^+(A)$ — число дорог, выходящих из $A$.

Предположим, что ни один город из $S$ не ведет в $B$. Тогда из-за полноты турнира для каждого $C \in S$ должна идти дорога

$$B \to C.$$

Но тогда из $B$ выходят дороги:

• в $A$,
• во все города из $S$.

Значит,

$$d^+(B) \ge |S|+1 = d^+(A)+1,$$

что противоречит выбору $A$ как города с максимальным числом исходящих дорог.

Следовательно, наше предположение неверно. Значит, существует такой город $C \in S$, что

$$A \to C \to B.$$

Итак, для любого города $B$:

• либо $A \to B$,
• либо существует промежуточный город $C$, что $A \to C \to B$.

То есть из города $A$ можно добраться до любого другого, проезжая не более одного промежуточного города.

Что и требовалось доказать.