Problem

Source:

Tags: combinatorics, graph theory



On a planet there are $M$ countries and $N$ cities. There are two-way roads between some of the cities. It is given that: (1) In each county there are at least three cities; (2) For each country and each city in the country is connected by roads with at least half of the other cities in the countries; (3) Each city is connceted with exactly one other city ,that is not in its country; (4) There are at most two roads between cities from cities in two different countries; (5) If two countries contain less than $2M$ cities in total then there is a road between them. Prove that there is cycle of lenght at least $M+\frac{N}{2}$.