A KML airline operates flights between several cities in such a way that from one city, you cannot directly reach more than three other cities. However, with at most one layover, you can get from anywhere to anywhere. What is the maximum number of cities between which the planes operate?
Let's examine a city, denoted as $A$. From this city, we can directly reach at most 3 other cities. From these 3 cities, we can directly reach at most $3 \cdot 2 = 6$ more cities, each from $3-3$, but one of these is $A$.

This results in at most 10 cities, including $A$. Since from $A$ we can reach only the already listed cities with at most one transfer, the cities are limited to 10.

This maximum number can indeed be achieved. Consider the following diagram, where each vertex represents a city, and the edges between them represent routes.

![](https://cdn.mathpix.com/cropped/2024_05_02_d33a06598b3907290f83g-1.jpg?height=485&width=512&top_left_y=435&top_left_x=796)

It is clear that exactly three edges originate from each vertex (i.e., exactly three routes originate from each city). It is also easy to verify that with at most one transfer, one can reach 9 other cities from any city (i.e., all the others). To verify this, it is sufficient to check 1 city from the "outer" and 1 city from the "inner" pentagon: from each, 3 other cities can be reached, and from those, $3 \cdot 2$ more can be reached, totaling 9.

Thus, the answer to the question is 10.

Note. It can be shown that such a flight route system exists for 2, 3, ..., 8 cities, but not for 9. Many incorrectly concluded from this that 8 is the maximum number.