Рассмотрим город, который связан с наибольшим количеством других городов (пусть этих городов n, и n >= 2. Если n = 1, то города разбиваются на пары, соединенные рейсами, рейсов не более 18/2 = 9, если n = 0, то рейсов 0). Тогда между любыми из этих n городов нет рейсов. Каждый из оставшихся 18 - 1 - n городов соединён не более с чем n городами, тогда общее число рейсов не больше, чем n + (18 - 1 - n) • n = n (18 - n).
n (18 - n) - квадратичная функция, максимум достигается в вершине n = 18/2 = 9, максимальное значение 81.
Пример, когда значение 81 достигается: пусть города разделены на две группы по 9, и из каждого города есть авиарейсы во все города другой группы. Тогда рейсов 9 * 9 = 81