Problem

Source: Korea National Olympiad 2nd Round 2019 #8

Tags: combinatorics, graph theory, hamiltonian cycle, matching



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.)