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

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

Ответ: 4.