a country has 1001 cities, and each two cities are connected
Source: Russian Olympiad 2004, problem 10.6
May 3, 2004
graph theorycombinatorics unsolvedcombinatorics
Problem Statement
A country has 1001 cities, and each two cities are connected by a one-way street. From each city exactly 500 roads begin, and in each city 500 roads end. Now an independent republic splits itself off the country, which contains 668 of the 1001 cities. Prove that one can reach every other city of the republic from each city of this republic without being forced to leave the republic.