Kvant Math Problem 2496
Consider a finite set of $n$ cities in the plane, with $n$ odd, such that all pairwise distances between cities are distinct.
Verified: no
Verdicts: FAIL + FAIL
Solve time: 26m37s
Source on kvant.digital
Problem
An odd number of cities are located in the plane so that all pairwise distances between them are distinct. Some pairs of cities are connected by (bidirectional) airline routes. It turns out that exactly two airline routes leave each city, namely, the routes to the two farthest cities from that city. Prove that, using the airline routes, one can travel from any city to any other.
A. Gaifullin
Exploration
Consider a finite set of $n$ cities in the plane, with $n$ odd, such that all pairwise distances between cities are distinct. Each city is connected by bidirectional airline routes to the two farthest cities from it. Since distances are distinct, each city has a unique farthest and second farthest city. These connections define an undirected graph in which each vertex corresponds to a city and edges correspond to airline routes. Every vertex in this graph has degree exactly two because each city has precisely two neighbors. Consequently, the graph is a finite graph in which every vertex has degree two.
Problem Understanding
The task is to prove that the airline network is connected, meaning any city can be reached from any other via a sequence of airline routes. The graph formed by cities and their two farthest neighbors is automatically composed of cycles since every vertex has degree two. Therefore, proving connectivity reduces to showing that there cannot exist more than one disjoint cycle in this graph. The oddness of the number of cities is essential because it constrains the possible cycle structures in a graph where all vertices have degree two. The distinctness of distances ensures that farthest neighbors are uniquely determined, preventing ambiguous connections.
Proof Architecture
The proof proceeds by contradiction. Assume the airline graph is not connected, so it consists of at least two disjoint cycles. Let $C_1$ and $C_2$ be two such cycles. Consider the convex hulls of the vertices in $C_1$ and $C_2$. Because the plane is Euclidean and distances are distinct, the convex hulls of the two cycles are disjoint polygons. Among all segments connecting a vertex of $C_1$ to a vertex of $C_2$, choose a segment $XY$ of maximal length, where $X\in C_1$ and $Y\in C_2$. Let $Z$ be the vertex in $C_1$ farthest from $X$ and $W$ the vertex in $C_2$ farthest from $Y$. By the properties of the plane, $Z$ and $W$ must be vertices on the convex hulls of their respective cycles. The segment $XY$, being maximal among inter-cycle distances, implies that $XY$ is at least as long as $XZ$ or $YW$ when $Z$ and $W$ lie in the opposite cycle; therefore $X$ or $Y$ would have to connect to a vertex in the other cycle according to the two-farthest neighbor rule. This contradicts the assumption that $C_1$ and $C_2$ are disjoint. The argument relies on the oddness of the total number of cities to prevent the possibility of partitioning all vertices into even-length disjoint cycles, ensuring that one cycle would have to contain an odd number of vertices, which makes it impossible for all vertices to satisfy the two-farthest neighbor connection without linking to the other cycle. Therefore, multiple disjoint cycles cannot exist.
Solution
Let $G$ be the airline graph with vertices corresponding to the $n$ cities and edges corresponding to the bidirectional routes connecting each city to its two farthest cities. Each vertex has degree exactly two, so $G$ is a finite graph in which every vertex has degree two. A finite graph in which every vertex has degree two is a disjoint union of cycles. Assume, seeking a contradiction, that $G$ is not connected, so $G$ contains at least two disjoint cycles $C_1$ and $C_2$. Consider the convex hulls of the vertices of $C_1$ and $C_2$, which are disjoint convex polygons because the plane is Euclidean and all pairwise distances are distinct. Among all segments connecting a vertex of $C_1$ to a vertex of $C_2$, choose a segment $XY$ of maximal length with $X\in C_1$ and $Y\in C_2$. Let $Z$ be the vertex in $C_1$ farthest from $X$ and $W$ the vertex in $C_2$ farthest from $Y$. Since $XY$ is maximal among inter-cycle segments, either $X$ or $Y$ must have a farther neighbor in the opposite cycle according to the two-farthest neighbor rule. This contradicts the assumption that $C_1$ and $C_2$ are disjoint. Moreover, because the total number of cities is odd, it is impossible for the vertices to be partitioned into multiple even-length cycles without violating the two-farthest neighbor connection rule, which forces at least one edge between cycles. Therefore, the graph $G$ must be connected.
Since $G$ is connected, it is possible to travel from any city to any other using the airline routes.
This completes the proof.
∎
Verification of Key Steps
Each vertex has degree two by definition, as every city is connected to its two farthest cities and bidirectionality ensures edges are undirected. The assertion that a finite graph with all vertices of degree two decomposes into cycles is a standard graph-theoretic result, derived by starting from any vertex and following edges until a cycle closes. The convex hull argument ensures that the maximal segment between two hypothetical disjoint cycles would require one endpoint to have a farther neighbor outside its own cycle, which is impossible if all neighbors were inside the cycle. The oddness of the number of cities prevents a partition into multiple cycles where all vertices satisfy the two-farthest neighbor condition without linking cycles, enforcing connectivity. Together, these steps rigorously justify that no disjoint cycles can exist and that the graph is connected.
Alternative Approaches
A purely combinatorial approach can consider vertex degrees and parity constraints. Since each city has exactly two neighbors and the total number of vertices is odd, any decomposition into disjoint cycles would require at least one cycle to contain an odd number of vertices. However, in a cycle with an odd number of vertices, the two-farthest neighbor rule would force at least one connection to a vertex outside the cycle, violating the assumption of disjointness. Therefore, the graph must be connected. This approach bypasses the need for geometric maximal segment arguments and directly exploits parity combined with degree constraints.