На планете есть городов. Пришельцы Матвей и Тимофей собираются связать их двусторонними авиарейсами. При этом не обязательно, чтобы из каждого города можно было добраться до каждого авиарейсами. За обозначим множество из городов такое, что каждые два

На планете есть $N$ городов. Пришельцы Матвей и Тимофей собираются связать их двусторонними авиарейсами. При этом не обязательно, чтобы из каждого города можно было добраться до каждого авиарейсами. За $K_{n}$ обозначим множество из $n \geq 1$ городов такое, что каждые два соединены авиарейсами. Назовём простым циклом длины $n \geq 3$ и обозначим $C_{n}$, последовательность из $n$ различных городов, в которой каждый следующий соединён с предыдущим (и последний с первым). Два простых цикла считаются различными, если в одном из них есть хотя бы один авиарейс, которого нет в другом.

Во всех пунктах ответ может зависеть от $N$. Во всех пунктах, даже если не был получен ответ, нахождение конфигурации, в которой максимальное число объектов достигается, уже представляет большой интерес.

1. К сожалению, Матвею не нравится, как выглядят пути длины 3, так что в получившейся системе авиарейсов их не будет. Какое наибольшее количество авиарейсов на планете может быть при таком условии? Путь длины 3 - три различных авиарейса такие, что второй начинается в городе, где заканчивается первый, а третий начинается там, где заканчивается второй.
2. Теперь Матвей запрещает строить простые циклы нечётной длины. Какое наибольшее количество авиарейсов на планете может быть? (В каждом пункте запреты в предыдущих пунктах не учитываются)
3. Матвей запрещает простые циклы нечётной длины. Какое наибольшее количество $C_{k}$ может быть?
4. Тимофей не любит полные подграфы и запрещает $K_{3}$. Какое наибольшее количество авиарейсов может быть?
5. Тимофей запрещает $K_{4}$. Какое наибольшее количество авиарейсов? Какое наибольшее количество $K_{3}$ ?
6. Матвей запрещает $C_{4}$. Какое наибольшее количество авиарейсов? $K_{3}$ ?
7. Тимофей запрещает $K_{3}$. Какое наибольшее количество $C_{4}$ ? $C_{m}$ ?
8. Тимофей запрещает $K_{4}$. Какое наибольшее количество $C_{4}$ ? $C_{m}$ ?
9. Тимофей запрещает $K_{n}$. Какое наибольшее количество $K_{m}$ ? $C_{m}$ ?
10. Матвей запрещает $C_{n}$. Какое наибольшее количество $K_{m}$ ? $C_{m}$ ?
11. Изменится ли что-нибудь, если жители планеты потребуют, чтобы из каждого города можно было добраться до каждого авиарейсами?
12. Предложите свои обобщения и дополнения к данной задаче.