а), б) Рассмотрим сразу общий случай. Разобьём все города каким-то образом на $k-1$ групп. Авиалинии, соединяющие два города из одной группы, назовём внутренними (для данного разбиения). Выберем из всех разбиений то, для которого число $N_{вн}$ внутренних авиалиний минимально, и докажем, что общее число $N$ авиалиний не меньше $(k-1)N_{вн}$.
Для этого заметим, что число $n$ внутренних авиалиний (для выбранного «минимального» разбиения), выходящих из любого города $A$, не больше числа $n_i$, авиалиний, ведущих из этого города в любую группу городов $G_i$ ($i=1$, $\ldots$, $k-1$): если бы оказалось, что $n\gt n_i$, мы перевели бы город $A$ в группу $G_i$ и тем самым уменьшили бы число внутренних авиалиний на $n-n_i$. Следовательно, общее число авиалиний, выходящих из города $A$, не меньше $(k-1)n$. Суммируя такие неравенства по всем городам и учитывая, что каждая авиалиния соединяет два города, получим, что $2N\ge 2(k-1)N_{вн}$. Закроем теперь все внутренние авиалинии нашего «минимального» разбиения. Тогда из любых $k$ городов хотя бы два попадут в одну группу и не будут соединены между собой, причём закрыты будут не более $\dfrac{N}{k-1}$ авиалиний.
