proposed by Alexander Gaifullin, Russia, it was also RMM Shortlist 2017 C1

Bump! Any solution?

Wonderful problem! Assume the contrary take a connected component with odd number of vertices and another one with even number of vertices. It is not hard to prove ,by length argument, that every two edge from different components cross each other. To finish, color the faces formed by edges of the component with odd vertices in black and white, properly. Every edge of the even component has started in the infinite face and ended in it so the number times it has crossed an edge from the odd component is even (in every crossing, the color changes). Contradiction.

Suppose there are multiple connected components; since each component is a $2$-regular graph, we have an union of disjoint cycles. Let $A$ and $B$ be $2$ such components. First, observe that any edge from $A$ must intersect any edge from $B$ (otherwise we could replace these two edges by the diagonals in the quadrilateral formed by the $4$ points, which would contradict the maximality of the distances between these points). Now take any edge from $A$ (say $L$) and keep moving from an edge to an incident one in $B$. Note that we keep switching semi-planes w.r.t $L$, so for us to have every segment intersecting $L$, we need to have an even number of vertices in B; analogously for A. Thus, we have reached to the conclusion that each of our connected components has an even number of vertices, so our entire graph has an even number of vertices. Contradiction!

This problem made me wish Aops would have a dislike button...

Problem's statement of problem is really confusing... The statement 'Each city is directly connected to exactly two ther cities, and the latter are located farthest from it.' should be changed to 'Each city is directly connected to exactly two other cities, which are the two farthest cities from it.' In other words, if two city $Y, Z$ are the farthest/second farthest city from $X$ each, $X$ is connected to $Y, Z$.