MathDB

For a positive integer

n

, there are two countries

A

and

B

with

n

airports each and

n^2-2n+ 2

airlines operating between the two countries. Each airline operates at least one flight. Exactly one flight by one of the airlines operates between each airport in

A

and each airport in

B

, and that flight operates in both directions. Also, there are no flights between two airports in the same country. For two different airports

P

and

Q

, denote by "

(P, Q)

-travel route" the list of airports

T_0, T_1, \ldots, T_s

satisfying the following conditions.
[*]

T_0=P,\ T_s=Q

[*]

T_0, T_1, \ldots, T_s

are all distinct. [*] There exists an airline that operates between the airports

T_i

and

T_{i+1}

for all

i = 0, 1, \ldots, s-1

.
Prove that there exist two airports

P, Q

such that there is no or exactly one

(P, Q)

-travel route.
[hide=Graph Wording]Consider a complete bipartite graph

G(A, B)

with

\vert A \vert = \vert B \vert = n

. Suppose there are

n^2-2n+2

colors and each edge is colored by one of these colors. Define

(P, Q)-path

a path from

P

Q

such that all of the edges in the path are colored the same. Prove that there exist two vertices

P

and

Q

such that there is no or only one

(P, Q)-path

Problem Statement