Problem

Source: XII International Festival of Young Mathematicians Sozopol 2023, Theme for 10-12 grade

Tags: combinatorics



In the country of Drilandia, which has at least three cities, there are bidirectional roads connecting some pairs of cities such that any city can be reached from any other. Two cities are called close if one can reach the other by using at most two intermediary cities. The mayor, Drilago, fortified the road system by building a direct road between each pair of close cities that were not already connected. Prove that after the expansion, there exists a journey that starts and ends at the same city, where each city except the first is visited exactly once, and the first city is visited twice (once at the beginning and once at the end).