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.
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 Crux Mathematicorum Sept 2000).© Copyright 2000 Stan Wagon. Reproduced with permission.