Problem of the Week 923

Diameter 2 Airlines

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:

1. for each town A there are exactly k direct flights leaving A, and they go to k distinct towns;
2. 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 Crux Mathematicorum Sept 2000).

© Copyright 2000 Stan Wagon. Reproduced with permission.