Algorithms on graphs
Source: St. Petersburg MO 2001, 11th grade, P2
April 24, 2023
algorithmgraphgraph theorycombinatorics
Problem Statement
There are 2000 cities in a country and no roads. Prove that some cities can be connected by a road such that there would be 2 cities with 1 road passing through them, there would be 2 cities with 2 roads passim through them,...,there would be 2 cities with 1000 roads passing through them.[I]Proposed by F. Bakharev