Олимпиадные задачи из источника «глава 6. Графы-1» для 8-11 класса - сложность 2 с решениями

В стране из каждого города выходит 100 дорог и от каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт.

Докажите, что и теперь от каждого города можно добраться до любого другого.

В Тридевятом царстве лишь один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов – по 20. Докажите, что из столицы можно долететь в Дальний (возможно, с пересадками).

Докажите, что граф с <i>n</i> вершинами, степень каждой из которых не менее ^<i>n</i>–1/₂, связен.