Road Networks and Reachability
Source:
October 31, 2024
combinatoricsChile
Problem Statement
In a country, there are 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.