2018 cities, some of which are connected by roads
Source: Dutch BxMO TST 2019 p5
January 10, 2020
combinatorics
Problem Statement
In a country, there are 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?