Question 76
There are 2012 cities in the land of Olympia. Some of the cities are connected by direct two-way routes (each route connects exactly two cities and no two routes connect the same pair of cities). It is known that no city is directly connected to more than 8 other cities. Prove that it is possible to close at most 2012 routes in such a way that among any four cities there will be two with no direct route between them.