Аба­жур можно рас­смот­реть как граф с 12-⁠ю вер­ши­на­ми, из ко­то­рых 8  — не­чет­ной сте­пе­ни. Если про­во­ло­ка про­хо­дит через вер­ши­ну, то она объ­еди­ня­ет два ребра, схо­дя­щи­е­ся в этой вер­ши­не, по­это­му в каж­дой вер­ши­не не­чет­ной сте­пе­ни хотя бы одна про­во­ло­ка долж­на на­чи­нать­ся или за­кан­чи­вать­ся. Вер­шин не­чет­ной сте­пе­ни 8, а у каж­дой про­во­ло­ки два конца, сле­до­ва­тель­но, по­тре­бу­ет­ся не менее че­ты­рех кус­ков про­во­ло­ки.

Как сде­лать аба­жур из че­ты­рех кус­ков, по­ка­за­но на ри­сун­ке: вый­дем из одной не­чет­ной вер­ши­ны (вер­ши­на 1 на ри­сун­ке, путь ука­зан оран­же­вы­ми стрел­ка­ми), за­кон­чим обход в дру­гой не­чет­ной вер­ши­не (вер­ши­на 6), а в каж­дую из вер­шин чет­но­го ин­дек­са зай­дем и вый­дем не­об­хо­ди­мое число раз. Остав­ши­е­ся вер­ши­ны 7 и 8, 9 и 10, 11 и 12 со­еди­ним еще тремя кус­ка­ми про­во­ло­ки.

Ответ: 4.

Рисуя граф так, как тре­бу­ет­ся в усло­вии, в каж­дую вер­ши­ну, за ис­клю­че­ни­ем на­чаль­ной и ко­неч­ной, нужно войти столь­ко же раз, сколь­ко выйти из нее. По­это­му в графе либо ровно две вер­ши­ны не­чет­ной сте­пе­ни (на­чаль­ная и ко­неч­ная), либо вер­шин не­чет­ной сте­пе­ни нет, если ко­неч­ная вер­ши­на сов­па­да­ет с на­чаль­ной.

У цен­траль­но­го графа че­ты­ре вер­ши­ны не­чет­но­го ин­дек­са. На­ри­со­вать его, не от­ры­вая ка­ран­да­ша от бу­ма­ги, не­воз­мож­но. Для осталь­ных не­труд­но при­ду­мать спо­соб.

Ответ: 4.

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

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

Ответ: 2.

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

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

Ответ: 3.

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

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

Ответ: 4.