123. In a certain state, the airline system is arranged in such a way that any city is connected by air routes to no more than three other cities, and from any city to any other, one can travel with no more than one layover.

What is the maximum number of cities that can be in this state?
123. Answer: 10 cities.

From any city $A$, one can reach no more than three cities, and from each of them no more than two (excluding $A$). Thus, the total number of cities is no more than $1+3+3 \cdot 2=$ $=10$.

The example in Fig. 60 shows that the required system of air routes in a state with ten cities exists.

$\nabla$ The graph in Fig. 60 is often used as an example and even has a special name, the "Petersen graph".