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

Да, это обязательно возможно.

Задача сводится к поиску Эйлерова цикла в графе. Эйлеров цикл существует тогда и только тогда, когда все вершины графа имеют чётную степень.

В данном случае сказано, что из каждого города выходит ровно две дороги. Это означает, что степень каждой вершины в графе равна 2.

Так как степень каждой вершины чётная, в этом графе существует Эйлеров цикл, который позволяет хоббиту пройти по каждой дороге ровно один раз и вернуться в исходный город (Шир).

Ответ: Да, обязательно возможно.