The not-so-hard-working flights

Consider three airports $A, B, C$ . Suppose $AB$ is the longest side; we claim that no flight goes between $AB$ . But this is trivial to see: a flight from $A$ will never choose $B$ , since $C$ is closer (and probably some other city is even closer, but basically not $B$ ), and likewise a flight from $B$ will never choose $A$ . Thus any pair of cities that is the longest side of some triangle can be immediately ruled off.

Suppose a city $A$ receives flights from the set of cities $S$ . We claim that for any two cities $B, C \in S$ , we have $\angle BAC > 60^\circ$ . This is easy to see, by remembering that the longest side of a triangle is always opposite the largest angle. Since there are flights along the pair $AB$ and $AC$ , this means $BC$ is the longest side, and hence $\angle BAC$ is the largest angle. But if $\angle BAC \le 60^\circ$ , this means we have the other two angles $\angle ABC, \angle ACB < 60^\circ$ . Their sum is less than $180^\circ$ , contradiction.

Now that angles between two cities in $S$ is greater than $60^\circ$ , simply sweep clockwise around $A$ . It will meet every city in $S$ once before returning to its original position; suppose we call the elements $S_1, S_2, S_3, \ldots, S_k$ in order met (and after $S_k$ , we continue until it meets $S_1$ again). Then $\angle S_i A S_{i+1} > 60^\circ$ for all $i$ (with $S_{k+1} = S_1$ ). Adding everything up gives $360^\circ > k \cdot 60^\circ$ , so $k \le 5$ . This is easily achievable.

Ivan's solution is based in geometry, but this is also a theorem of weighted graphs. A nearest-neighbor graph is the directed graph obtained from a weighted graph by connecting each vertex to its nearest neighbour. If the original graph is in general position (so that all distances between vertices are different), this is a planar graph with each vertex having valency at most $\boxed{5}$ .

Not a strict proof , Just a way to 'get' the answer If we have two airports: and suppose A is the one that has most 'origin' So , when we add the third airport (which is a origin of A) to the country,It can't be located in the circle , or above the line. That means θ will always be less than 60 degrees. One by one we add other airports (origins of A) to the country, they are all supposed to have a θ bigger than 60 degrees. Their sum can't be greater than 180° , So the origins of A should be less than 6 , wich is 5.