# Problem 8. (4 points)

In the Magic Country, there are 100 cities, some of which are connected by two-way air routes. Any two cities can be reached from each other with no more than 11 transfers, and there is a unique way to do so. If it is impossible to travel from city $A$ to city $B$ with 10 or fewer transfers, both cities are called peripheral. What is the maximum number of peripheral cities that can exist in the country?
Answer: 89

## Solution:

Consider two peripheral cities and the route between them. All 11 cities where transfers are made on this route cannot be peripheral. All other cities can be peripheral if there are direct flights from them to the first or last of these 11 intermediate cities.

Thus, the maximum number of peripheral cities is $100-11=89$.