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(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 N4n is an even integer. (Here, note that two exotic traveling courses are different if their starting place are different.)