Graphistan has 2019 cities and Graph Air (GA) is running one-way flights between all pairs of these cities. Determine the maximum possible value of the integer k such that no matter how these flights are arranged it is possible to travel from any city to any other city in Graphistan riding only GA flights so long as the absolute values of the difference between the number of flights originating and terminating at any city is not more than k.
Correct Solutions by,
- Toshihiro Shimizu Kawasaki, Japan
- Mehmet Ali Yıldırım Boğaziçi University, Istanbul
- Roger Bengtsson Lund, Sweden