Рас­смот­рим каж­дый кусок про­во­ло­ки как путь в графе. Если он на­чи­на­ет­ся и за­кан­чи­ва­ет­ся в раз­ных вер­ши­нах, то он со­дер­жит не­чет­ное число ребер, ис­хо­дя­щих из этих вер­шин, и чет­ное число ребер, ис­хо­дя­щих из любой дру­гой вер­ши­ны, по­то­му что все они раз­би­ва­ют­ся на пары «вхо­дя­щее ребро  — ис­хо­дя­щее ребро» за ис­клю­че­ни­ем пер­во­го и по­след­не­го. Если пусть на­чи­на­ет­ся и за­кан­чи­ва­ет­ся в одной вер­ши­не, то для нее число вер­шин также будет четно. Зна­чит, любая вер­ши­на не­чет­ной сте­пе­ни долж­на слу­жить на­ча­лом или кон­цом ми­ни­мум од­но­го из таких путей. Сле­до­ва­тель­но, их ко­ли­че­ство не мень­ше   — есть 4 вер­ши­ны не­чет­ной сте­пе­ни, каж­дый путь имеет не более двух кон­цов.

При­мер, по­ка­зы­ва­ю­щий, что можно обой­тись двумя пу­тя­ми, изоб­ра­жен на ри­сун­ке. Точки свар­ки обо­зна­че­ны зе­ле­ным для точек на­ча­ла об­хо­дов и крас­ным для точек кон­цов об­хо­дов цве­та­ми со­от­вет­ствен­но.

Ответ: 2.