MathDB

Let

n\ge 3

be an integer. In a country there are

n

airports and

n

airlines operating two-way flights. For each airline, there is an odd integer

m\ge 3

, and

m

distinct airports

c_1, \dots, c_m

, where the flights offered by the airline are exactly those between the following pairs of airports:

c_1

and

c_2

;

c_2

and

c_3

;

\dots

;

c_{m-1}

and

c_m

;

c_m

and

c_1

.
Prove that there is a closed route consisting of an odd number of flights where no two flights are operated by the same airline.

3