Problem

Source: Azerbaijan IZhO TST 2018 P4

Tags: combinatorics, TST, AZE IzHO TST



There are $10$ cities in each of the three countries. Each road connects two cities from two different countries (there is at most one road between any two cities.) There are more than $200$ roads between these three countries. Prove that three cities, one city from each country, can be chosen such that there is a road between any two of these cities.