0243 combinatorics 2nd edition Round 4 p3
Source:
May 10, 2021
combinatorics2nd edition
Problem Statement
In a country there are 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 , such that each of the remaining cities would be connected by a road with at least one of the two chosen cities.