FI-MO 2016 Problem 5

The ruler of Laputa will set up a train network between cities in the state, which satisfies the following conditions:

• Uniformity: From one city to another, by train, possibly through exchanges.
• Prohibition N: There exist no four cities $A, B, C, D$ such that there are direct routes between $A$ and $B, B$ and $C$ , and $C$ and $D$ , but taking a shortcut is not possible, that is, there are no direct rout between $A$ and $C, B$ and $D$ , or $A$ and $D$ . In addition, a direct airliner connection will be established exactly between their city pairs, with no direct train connection. Prove that the airline network is not connected when there is more than one city.