KMO 2021 Problem 4

For a positive integer $n$ , there are two countries $A$ and $B$ with $n$ airports each and $n^2-2n+ 2$ airlines operating between the two countries. Each airline operates at least one flight. Exactly one flight by one of the airlines operates between each airport in $A$ and each airport in $B$ , and that flight operates in both directions. Also, there are no flights between two airports in the same country. For two different airports $P$ and $Q$ , denote by "$(P, Q)$ -travel route" the list of airports $T_0, T_1, \ldots, T_s$ satisfying the following conditions.

• $T_0=P,\ T_s=Q$
• $T_0, T_1, \ldots, T_s$ are all distinct.
• There exists an airline that operates between the airports $T_i$ and $T_{i+1}$ for all $i = 0, 1, \ldots, s-1$ .

Prove that there exist two airports $P, Q$ such that there is no or exactly one $(P, Q)$ -travel route.