Графы продолжение

В стране Семерка 15 городов, каждый из которых соединен дорогами не менее, чем с 7 другими. Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через другие города).

Задача 1

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

Задача 2

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

Задача 3

Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту ровно один раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил? б) с него начал, но не на нем закончил? в) с него начал и на нем закончил?

Задача 4

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

Задача 5

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

Задача 6