some of these cities are connected by airlines
Source: Russian Olympiad 2004, problem 11.7
May 4, 2004
inductioninequalitiescombinatorics unsolvedcombinatorics
Problem Statement
In a country there are several cities; some of these cities are connected by airlines, so that an airline connects exactly two cities in each case and both flight directions are possible. Each airline belongs to one of flight companies; two airlines of the same flight company have always a common final point. Show that one can partition all cities in groups in such a way that two cities from exactly the same group are never connected by an airline with each other.