Travel Logic (mod. 4)

Question

There are two airlines A and B and finitely many airports. For each pair of airports, there is exactly one airline among A and B whose flights operates in both directions. Each airline plans to develop world travel packages which pass each airport exactly once using only its flights. Let $a$ and $b$ be the number of possible packages which belongs to A and B respectively. Prove that $a-b$ is a multiple of $4$.

What I thought: Let $n$ be the number of airports. We may need the restriction $n \ge 4$.

Answer 1

This answer uses the rules suggested by @MikeEarnest. We shall also adopt the convention of considering paths $v_1 v_2 ... v_i$ and $v_i ... v_2 v_1$ to be distinct.

Preliminary result Let $E$ be any set of edges in $K_n$. If $|E|<n-1$ then the number of Hamiltonian paths using all the edges of $E$ is a multiple of $4$.

We can assume the edges of $E$ are part of at least one Hamiltonian path otherwise we are finished. Let the graph on $E$ have $c$ components and $n-v$ vertices. For each arrangement of the components and the extra $v\ge 2$ vertices in a line we can permute the components and the vertices in $(c+v)!$ ways and this will be divisible by 4 unless $c=1, v=2$.

In the latter case, the component has more than one vertex and so has two orientations. For each of these there are six placings for the extra vertices giving 12 Hamiltonian paths in total.

Proof that $a\equiv b \mod 4$.

Let the edges of $K_n, n\ge 4$ be partitioned as $X\cup R \cup B$ where $R$ and $B$ are edges coloured red and blue, respectively.

Given that the edges of $X$ are coloured blue, define $N_B(X,R,B)$ to be the number of Hamiltonian paths in the blue graph which must use the edges of $X$. Given that the edges of $X$ are coloured red, define $N_R(X,R,B)$ to be the number of Hamiltonian paths in the red graph which must use the edges of $X$.

The result we need to prove is therefore $N_R(\phi,R,B)-N_B(\phi,R,B)\equiv 0 \mod 4$

General result $N_R(X,R,B)-N_B(X,R,B)\equiv 0 \mod 4$

We shall proceed by induction on $|B|$.

Let $e$ be any edge of $B$. Then, by considering paths using and not using $e$ we see that $$N_B(X,R,B)=N_B(X\cup \{e\},R,B/\{e\})+N_B(X,R\cup \{e\},B/\{e\})$$ Similarly $$N_R(X,R\cup \{e\},B/\{e\})=N_R(X\cup \{e\},R,B/\{e\})+N_R(X,R,B)$$

The quantity $N_R(X,R,B)-N_B(X,R,B)$ is therefore given by the difference of two quantities of the same form but with smaller $|B|$. It is therefore sufficient to prove the result when $|B|=0$.

If $|X|\ne n-1$ then $N_B(X,R,\phi)=0$ and the result follows from the Preliminary result. So suppose $|X|= n-1$. Then $N_R(X,R,\phi)=N_B(X,R,\phi)$ is $2$ or $0$ depending upon whether the edges of $X$ form or do not form a Hamiltonian cycle.

Answer 2

This result appears to be false.

Example 1. Let R,S,T,U be airports with Airline A operating in both directions between R&S, S&U and U&T, and Airline B operating in both directions between the other three pairs of airports. In addition, let Airline A operate flights from U to R and S to T.

Then Airline B has $0$ possible world travel packages. (Assuming it requires a closed path visiting each airport precisely once.)

Airline A has $1$ possible world travel package U-R-S-T-U.

(If you count this as 4 packages then see Example 2.)

Example 2. Let R,S,T,U,V be airports with Airline A operating in both directions between R&S and V&R and Airline B operating in both directions between all the other pairs of airports. In addition, let Airline A operate flights from s to T,T to U and U to V.

Then Airline B has $0$ possible world travel packages. (Assuming it requires a closed path visiting each airport precisely once.)

Airline A has $1$ possible world travel package R-S-T-U-V-R. You may wish to count this as 5 packages.

(If $a$ and $b$ count Hamiltonian paths not cycles then see Example 3.)

Example 3. Let R,S,T,U be airports with Airline A operating in both directions between all pairs of airports and Airline B only operating flights from R to S and S to T and T to U.

Then $a=4!$ and $b=1$.