2001 towns in a country
Source: All-Russian MO 2001 Grade 11 #7
January 3, 2012
graph theorycombinatorics unsolvedcombinatorics
Problem Statement
The towns in a country are connected by some roads, at least one road from each town, so that no town is connected by a road to every other city. We call a set of towns dominant if every town not in is connected by a road to a town in . Suppose that each dominant set consists of at least towns. Prove that the country can be partitioned into republics in such a way that no two towns in the same republic are connected by a road.