\section*{Problem 9}

Every city in a certain state is directly connected by air with at most three other cities in the state, but one can get from any city to any other city with at most one change of plane. What is the maximum possible number of cities?


\section*{Solution}

Answer: 10.

Take a particular city X. At most 3 cities are directly connected to X. Each of those is directly connected to at most 2 other cities (apart from \(\mathrm{X}\) ). So \(\mathrm{X}\) is connected with at most one change to at most 9 other cities. Thus the maximum number is at most 10 .

We can achieve 10 as follows. Label the cities \(1, \ldots, 10\). Make direct connections as follows: \(1: 2,3,4 ; 2: 1,5,6 ; 3: 1,7,8 ; 4: 1,9,10 ; 5: 2,7,9 ; 6: 2,8,10 ; 7: 3,5,10 ; 8: 3,6,9 ;\) \(9: 4,5,8 ; 10: 4,6,7\)

