ASU 560 Commonwealth of Independent States 1992 n cities, gold route
Source:
August 14, 2019
combinatorics
Problem Statement
A country contains 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 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.