MathDB

In neverland, there are

n

cities and

n

airlines. Each airline serves an odd number of cities in a circular way, that is, if it serves cities

c_1,c_2,\dots,c_{2k+1}

, then they fly planes connecting

c_1c_2,c_2c_3,\dots,c_1c_{2k+1}

. Show that we can select an odd number of cities

d_1,d_2,\dots,d_{2m+1}

such that we can fly

d_1\rightarrow d_2\rightarrow\dots\rightarrow d_{2m+1}\rightarrow d_1

while using each airline at most once.

2