Track / Stage 6 / 308 of 400 #1308 of 1964

Problem 1308

National olympiad, first round

Combinatorics Difficulty 6.6 Prove it

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 "[i] $(P, Q)$ -travel route[/i]" the list of airports $T_0, T_1, \ldots, T_s$ satisfying the following conditions.
[list]
[*] $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$ .
[/list]
Prove that there exist two airports $P, Q$ such that there is no or exactly one [i] $(P, Q)$ -travel route[/i].

[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$ to $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$ . [/hide]

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Restate the problem in graph-theoretical terms:
- We have a bipartite graph $G(A, B)$ where $|A| = |B| = n$ .
- There are $n^2 - 2n + 2$ colors, and each edge in $G$ is colored with one of these colors.
- Each color is used on at least one edge.
- We need to prove that there exist two vertices $P$ and $Q$ such that there is no or exactly one $(P, Q)$ -path, where a $(P, Q)$ -path is a path from $P$ to $Q$ such that all edges in the path are the same color and all vertices in the path are distinct.

2. Initial observations:
- The total number of edges in a complete bipartite graph $K_{n,n}$ is $n^2$ .
- Since we have $n^2 - 2n + 2$ colors, there are $2n - 2$ edges that are not used.

3. Consider the structure of the graph:
- Each vertex in $A$ is connected to each vertex in $B$ by a unique edge.
- Since there are $n^2 - 2n + 2$ edges, we can think of removing $2n - 2$ edges from the complete bipartite graph $K_{n,n}$ .

4. **Analyze the implications of removing $2n - 2$ edges:**
- Removing $2n - 2$ edges from $K_{n,n}$ means that some vertices in $A$ and $B$ will have fewer connections.
- Specifically, each vertex in $A$ and $B$ will have at least $n - 2$ connections remaining.

5. Consider the coloring of the edges:
- Each color is used on at least one edge.
- Since there are $n^2 - 2n + 2$ colors, each color corresponds to a unique edge or a set of edges.

6. **Prove the existence of $P$ and $Q$ with no or exactly one $(P, Q)$ -path:**
- Suppose for contradiction that for every pair of vertices $P$ and $Q$ , there are at least two $(P, Q)$ -paths.
- This would imply that there are multiple paths of the same color connecting $P$ and $Q$ , which contradicts the fact that we have removed $2n - 2$ edges and each color is used on a unique set of edges.

7. Conclusion:
- Therefore, there must exist at least one pair of vertices $P$ and $Q$ such that there is no or exactly one $(P, Q)$ -path.

$\blacksquare$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.