5. Какое наименьшее число рёбер придется пройти дважды, чтобы обойти все рёбра икосаэдра и вернуться в исходную вершину?

Решение:

Икосаэдр — это выпуклый многогранник, состоящий из 20 граней (треугольников), 30 ребер и 12 вершин. В каждой вершине икосаэдра сходятся 5 ребер.

Для того чтобы обойти все ребра графа и вернуться в исходную вершину, необходимо, чтобы степень каждой вершины была четной (теорема Эйлера о китайском городе). В икосаэдре степень каждой вершины равна 5, что является нечетным числом.

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

В икосаэдре 12 вершин, и каждая имеет нечетную степень (5). Чтобы сделать степень каждой вершины четной, нам нужно увеличить степень каждой из 12 вершин на 1 (с 5 до 6). Для этого нам нужно добавить 12/2 = 6 дополнительных ребер, которые будут проходить дважды.

Эти 6 ребер образуют минимальный набор для того, чтобы сделать все вершины четными. Попарное соединение вершин с нечетной степенью минимизирует количество удвоенных ребер.

Минимальное число ребер, которое придется пройти дважды, равно половине числа вершин с нечетной степенью.

Число вершин с нечетной степенью = 12.

Наименьшее число ребер, которое придется пройти дважды = 12 / 2 = 6.

Ответ: 6