Арагорн хочет соединить 9 крепостей дорогами так, чтобы из одной в другую можно было попасть не более чем с двумя пересадками. Каждая дорога должна соединять две крепости, и дороги не должны пересекаться. Из одной крепости не должно выходить более трёх дорог. Схематичное расположение крепостей показано на рисунке.
Можно ли решить задачу Арагорна? Если нет, то поясните ответ. Если да, то предложите решение с минимально возможным количеством дорог.

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

У меня получилось какое-то такое решение.
Схема дорог симметрична. Если убрать дороги,помеченные зелёным,то схема так же останется симметричной. Думаю,это не единственное оптимальное решение(если оно оптимальное). На ум приходит только доказательство оптимальности перебором(динамическ�ое программирование или генетические алгоритмы).