В государстве система авиалиний устроена таким образом, что любой город соединен авиалиниями не более чем с тремя другими

Ответ: 10 городов. Из любого города   можно добраться не более, чем до трех городов, а из каждого из них не более, чем до двух (не считая  ). Итак, всего городов не более 1+3+6 = 10 Пример на рисунке (граф Петерсона) показывает существование нужной системы авиалиний