5. In the country of Betia, there are 125 cities, some of which are connected by express trains that do not stop at intermediate stations. It is known that any four cities can be toured in a circle in some order. What is the minimum number of pairs of cities connected by express trains?
Answer: 7688.

Solution. Suppose that some city (let's call it Betsk) is connected by express trains to no more than 122 cities. Take a quartet of cities consisting of Betsk and any three other cities, two of which Betsk is not connected to. This quartet cannot be traveled in a circle, otherwise Betsk must be connected to at least two cities: one to arrive from, and another to depart to. Therefore, each city is connected to at least 123 cities. Consequently, the total number of pairs of cities connected by express trains is no less than $\frac{123 \cdot 125}{2}=7687 \frac{1}{2}$. But the number of pairs must be an integer, so it is at least 7688.

Now, let's show that the number of pairs of cities can be exactly 7688. Number the cities from 1 to 125 and connect by express trains all pairs of cities, except for pairs with numbers $2k-1$ and $2k$ for $k=1,2, \ldots, 62$. Let's verify that this construction satisfies the problem's condition. Since each city is connected by express trains to 123 cities, and the 125th city is connected to 124 cities, the total number of pairs of connected cities is $\frac{1}{2}(124 \cdot 123 + 124) = 7688$. Now, take any quartet of cities $A, B, C, D$. In this quartet, each city is connected to at least two of the others. Suppose that $B$ is connected to $A$ and $C$. If $D$ is also connected to $A$ and $C$, then the route $A \rightarrow B \rightarrow C \rightarrow D \rightarrow A$ works. Otherwise, $D$ is not connected to exactly one of the cities $A$ and $C$ (let it be $C$). Then $C$ is connected to $A$, and $D$ is connected to $B$, and the cities can be traveled in a circle $A \rightarrow C \rightarrow B \rightarrow D \rightarrow A$.

![](https://cdn.mathpix.com/cropped/2024_05_06_66368caef28b3de8e403g-08.jpg?height=237&width=240&top_left_y=2052&top_left_x=974)