MathNet 1969 — Part 01 Question 5

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?