2000 cities, 2N +2 republics - All-Russian MO 2000 Regional (R4) 10.8
Source:
September 26, 2024
combinatorics
Problem Statement
There are cities in the country, some pairs of cities are connected by roads. It is known that no more than different non-self-intersecting cyclic routes of odd length. Prove that the country can be divided into republics so that no two cities from the same republic are connected by a road.