Problem

Source: Dutch BxMO TST 2019 p5

Tags: combinatorics



In a country, there are $2018$ 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?