MathNet 2005 — Part 03 Question 76

In a country with $n+1$ cities, there are two-way flights between some of these cities. A two-way flight between cities $A$ and $B$ means that within the same day there is a flight from $A$ to $B$ as well as one from $B$ to $A$, while there is no one-way flight from a city to another. There may be more than one two-way flight between two cities. We denote the total number of take-offs from city $A$ within one day by $d_A$. For all cities $A$ except for the capital, one has $d_A \le n$. Moreover, for any two cities $A$, $B$ both different than the capital, one has $d_A + d_B \le n$, if there is no two-way flight between $A$ and $B$. There is no restriction on the number of flights from the capital, which is naturally included among the $n+1$ cities.
Find the maximal number of two-way flights that can be made within a day in this country and determine all flight schedules with this maximal number of two-way flights.