Question 70
A country contains $n$ cities and some towns. There is at most one road between each pair of towns and at most one road between each town and each city, but all the towns and cities are connected, directly or indirectly. We call a route between a city and a town a gold route if there is no other route between them which passes through fewer towns. Show that we can divide the towns and cities between $n$ republics, so that each belongs to just one republic, each republic has just one city, and each republic contains all the towns on at least one of the gold routes between each of its towns and its city.