MathDB

There are two countries

A

and

B

, where each countries have

n(\ge 2)

airports. There are some two-way flights among airports of

A

and

B

, so that each airport has exactly

3

flights. There might be multiple flights among two airports; and there are no flights among airports of the same country. A travel agency wants to plan an exotic traveling course which travels through all

2n

airports exactly once, and returns to the initial airport. If

N

denotes the number of all exotic traveling courses, then prove that

\frac{N}{4n}

is an even integer.
(Here, note that two exotic traveling courses are different if their starting place are different.)

Problem Statement