If a country has 25 towns, what is the smallest k such that a flight schedule connecting the towns can be set up so that:

- for each town A there are exactly k direct flights leaving A, and they go to k distinct towns;
- if there is no direct flight from A to B, there is a town C with flights from C to A and C to B.

Note:

In the original problem, from the Vietnamese Olympiad, flights go both ways. That is, if there is a flight from A to B then there is a flight from B to A and the underlying graph is undirected.Another interesting problem is to consider the graph directed. Then part (b) should say: if there is no direct flight from A to B, there is a town C with flights from A to C and C to B.

Source: Vietnamese 1997 Olympiad Selection (in© Copyright 2000 Stan Wagon. Reproduced with permission.Crux MathematicorumSept 2000).

16 November 2000