MathDB

4.3

Part of MathLinks Contest 2nd

Problems(1)

0243 combinatorics 2nd edition Round 4 p3

Source:

5/10/2021
In a country there are 100100 cities, some of which are connected by roads. For each four cities there are at least two roads between them. Also, there is no path that passes through each city exactly one time. Prove that one can choose two cities among those 100100, such that each of the 9898 remaining cities would be connected by a road with at least one of the two chosen cities.
combinatorics2nd edition