Question 8
Graph Airlines (GA) operates flights between some of the cities of the Republic of Graphia. There are GA flights between each city and at least three different cities and it is possible to travel from any city to any other city in the Republic of Graphia using GA flights. 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 from any city to any other city using GA flights, yet at least $\frac{2}{9}$ of the cities has only one flight.