MathDB

P4

Part of 2021 Korea National Olympiad

Problems(1)

Travel Route in a Bipartite Graph

Source: KMO 2021 P4

11/14/2021
For a positive integer nn, there are two countries AA and BB with nn airports each and n2−2n+2n^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 AA and each airport in BB, and that flight operates in both directions. Also, there are no flights between two airports in the same country. For two different airports PP and QQ, denote by "(P,Q)(P, Q)-travel route" the list of airports T0,T1,…,TsT_0, T_1, \ldots, T_s satisfying the following conditions.
[*] T0=P, Ts=QT_0=P,\ T_s=Q [*] T0,T1,…,TsT_0, T_1, \ldots, T_s are all distinct. [*] There exists an airline that operates between the airports TiT_i and Ti+1T_{i+1} for all i=0,1,…,s−1i = 0, 1, \ldots, s-1.
Prove that there exist two airports P,QP, Q such that there is no or exactly one (P,Q)(P, Q)-travel route.
[hide=Graph Wording]Consider a complete bipartite graph G(A,B)G(A, B) with ∣A∣=∣B∣=n\vert A \vert = \vert B \vert = n. Suppose there are n2−2n+2n^2-2n+2 colors and each edge is colored by one of these colors. Define (P,Q)−path(P, Q)-path a path from PP to QQ such that all of the edges in the path are colored the same. Prove that there exist two vertices PP and QQ such that there is no or only one (P,Q)−path(P, Q)-path.
combinatoricsgraph theorybipartite graph