Folklore

In a certain state, the airline system is arranged in such a way that each city is connected by air routes to no more than three other cities, and from any city, you can reach any other city with no more than one layover. What is the maximum number of cities that can be in this state?
Evaluation. From a fixed city $A$, one can directly reach no more than three cities, and with one transfer - no more than $3 \cdot 2=6$ additional cities. Thus, the total number of cities can be no more than ten. An example of a network of 10 cities is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_6fdbe810ffc70cc86b90g-35.jpg?height=495&width=554&top_left_y=1679&top_left_x=749)

## Answer

10. 

Submit a comment