Не­труд­но при­ду­мать обход, в ко­то­ром два­жды про­хо­дят­ся толь­ко 9  ребер. До­ка­жем, что это ми­ни­маль­ное ко­ли­че­ство.

При об­хо­де не­об­хо­ди­мо выйти из на­чаль­ной вер­ши­ны, войти и выйти изо всех осталь­ных вер­шин, кроме ко­неч­ной, затем войти в ко­неч­ную вер­ши­ну. Сле­до­ва­тель­но, каж­дая из 18 про­ме­жу­точ­ных вер­шин до­де­ка­эд­ра долж­на быть прой­де­на чет­ное число раз. В  вер­ши­нах схо­дят­ся по три ребра, по­это­му по­на­до­бит­ся один до­пол­ни­тель­ных выход, а всего их долж­но быть не менее 18. Каж­дой паре выход-вход со­от­вет­ству­ет одно ребро, а по­то­му не­об­хо­ди­мо не менее де­вя­ти про­хо­дов по реб­рам.

Ответ: 9.