5. В королевстве 1001 город. Король приказал проложить между городами дороги так, чтобы из каждого города выходило ровно 7 дорог. Смогут ли подданные справиться с приказом?

Посчитаем сумму числа дорог, выходящих из всех городов:

\(1001\cdot 7=7007\).

При этом каждая дорога посчитана дважды — по одному разу для каждого из двух городов, которые она соединяет. Поэтому сумма степеней всех вершин графа должна быть чётной: она равна удвоенному числу дорог.

Число \(7007\) нечётно, что невозможно.

Ответ: нет, не смогут.