Задача М743‍‍

В стране $N$‍‍ городов.

1. Между любыми двумя городами имеется прямое сообщение самолётом или пароходом. Докажите, что, пользуясь лишь каким-то одним видом транспорта, из любого города можно попасть в любой другой (быть может, с пересадками).
2. Между любыми двумя городами имеется прямое сообщение самолётом, поездом или пароходом. Докажите, что можно выбрать не менее $\dfrac{N}{2}$‍‍ городов и один из трёх видов транспорта так, что, пользуясь им одним, из любого выбранного города можно попасть в любой другой выбранный город.
3. Приведите пример, доказывающий, что в утверждении б) заменить число $\dfrac{N}{2}$‍‍ бо́льшим, вообще говоря, нельзя.