THE 68th NMO SELECTION TESTS FOR THE BALKAN AND INTERNATIONAL MATHEMATICAL OLYMPIADS

Consider the graph $G$ whose vertices are the cities and whose edges are the direct two-way flights. We must show that $G$ is connected.

Assuming $G$ has at least two components, we show that the cardinality of each component is even; this contradicts the fact that the total number of vertices is odd, whence the conclusion.

Lemma. If $AB$ and $XY$ are edges in different components of $G$, then the segments $AB$ and $XY$ cross at an interior point.

Proof. Two cases are to be ruled out:

(1) The lines $AB$ and $XY$ meet outside both open segments $(AB)$ and $(XY)$, possibly at an ideal point; that is, after a suitable relabelling (if necessary), $ABXY$ is a convex (possibly degenerate) quadrangle. In this case, the segments $AX$ and $BY$ cross at some point $O$, so $AX+BY=(OA+OX)+(OB+OY)=(OA+OB)+(OX+OY)\ge AB+XY$. Consequently, either $AX\ge AB$, in which case $A$ is connected to $X$, contradicting the fact that the two lie in different components of $G$; or $BY\ge XY$, in which case $Y$ is connected to $B$, contradicting the fact that the two lie in different components of $G$.

(2) The lines $AB$ and $XY$ cross at an interior point of exactly one of open segments $(AB)$ and $(XY)$, say, the latter; that is, after a suitable relabelling (if necessary), the segment $AB$ lies inside the triangle $AXY$. In this case, $AB<\max (AX,AY)$, since the segment $AB$ lies along a cevian in the triangle $AXY$, so $A$ is connected to (exactly) one of $X$ and $Y$, contradicting the fact that $A$ and $X$, $Y$ lie in different components of $G$.

Back to the problem, since every vertex has degree $2$, each component of $G$ is a circuit. Let $C$ be one such and let $XY$ be an edge of $G$ whose endpoints do not belong to $C$. By the lemma, every two consecutive vertices of $C$ lie on opposite sides of the line $XY$, so $C$ has an even number of vertices. This ends the proof.