9.4. In the country, there are 20 cities. An airline wants to organize two-way flights between them so that from any city, it is possible to reach any other city with no more than $k$ transfers. At the same time, the number of air routes from any city should not exceed four. What is the smallest $k$ for which this is possible?

## 9th grade

## Second day
9.4. Answer. $k=2$.

Note that at least two transfers will be required. Indeed, from an arbitrary city $A$ without a transfer, one can reach no more than 4 cities, and with exactly one transfer - no more than $4 \cdot 3=12$ cities (since one of the flights from each of these cities leads back to $A$). Therefore, if using no more than one transfer, one can reach no more than 16 other cities from any city, but it is required

![](https://cdn.mathpix.com/cropped/2024_05_06_695363564d40540a0226g-2.jpg?height=357&width=505&top_left_y=227&top_left_x=410)

Fig. 4

![](https://cdn.mathpix.com/cropped/2024_05_06_695363564d40540a0226g-2.jpg?height=494&width=511&top_left_y=158&top_left_x=1138)

Fig. 5

- to reach 19. In Fig. 5, it is shown how flights can be organized so that there are no more than two transfers. The diagram is symmetric, so it is sufficient to show how to reach from the first city to any other. From it, without a transfer, one can reach cities $2,3,4,5$. Then with one transfer to cities $6,7,8$ (from 5), 9 (from 2), 13 (from 3), and 17 (from 4). And with two transfers - to cities 10, 11, 12 (from 9), to 14, 15, 16 (from 13), to $18,19,20$ (from 17).