A tale of (not so) many citiesDiscrete Mathematics Level 3
The Queen plans to build a number of new cities in the wilderness, connected by a network of roads. She expects the annual tax revenues from each city to be numerically equal to the square of the population. Road maintenance will be expensive, though. The annual cost for each road is expected to be numerically equal to the product of the populations of the two cities that road connects. To keep the costs for road maintenance down, the Queen decrees that there should be only one way to get from any city to any other, and not more than three roads should connect to any given city (the attached design would be acceptable, for example). What is the largest number of cities the Queen can build without risking to lose money, regardless of the populations of the new cities and the design of the roads (subject to the two constraints mentioned above)?