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

а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

б) Какое наименьшее число раз придется ломать проволоку, чтобы всё же изготовить требуемый каркас?

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

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

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

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

Доска имеет форму креста, который получается, если из квадратной доски 4×4 выкинуть угловые клетки.

Можно ли обойти её ходом шахматного коня и вернуться на исходное поле, побывав на всех полях ровно по разу?