Problem

Source:

Tags: combinatorics, Chile



In a country, there are \( n \) cities. Each pair of cities is connected either by a paved road or a dirt road. It is known that there exists a pair of cities such that it is impossible to travel between them using only paved roads. Show that, in this case, it is possible to travel between any two cities using only dirt roads.