MathDB

5

Part of 2019 Dutch BxMO TST

Problems(1)

2018 cities, some of which are connected by roads

Source: Dutch BxMO TST 2019 p5

1/10/2020
In a country, there are 20182018 cities, some of which are connected by roads. Each city is connected to at least three other cities. It is possible to travel from any city to any other city using one or more roads. For each pair of cities, consider the shortest route between these two cities. What is the greatest number of roads that can be on such a shortest route?
combinatorics