MathDB

4

Part of TNO 2023

Problems(1)

Road Networks and Reachability

Source:

10/31/2024
In a country, there are n 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.
combinatoricsChile