MathDB
Graph Airlines (GA)

Source: Turkey National Olympiad 2002 - D1 - P3

December 7, 2009
combinatorics unsolvedcombinatorics

Problem Statement

Graph Airlines (GA) (GA) operates flights between some of the cities of the Republic of Graphia. There are at least three GA GA flights from each city, and it is possible to travel from any city in Graphia to any city in Graphia using GA GA flights. GA GA decides to discontinue some of its flights. Show that this can be done in such a way that it is still possible to travel between any two cities using GA GA flights, yet at least 2/9 2/9 of the cities have only one flight.
Back to ProblemsView on AoPS