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

Решение:

Додекаэдр — это многогранник, у которого 12 граней, 20 вершин и 30 рёбер. Каждая вершина имеет степень 3 (из каждой вершины выходит 3 ребра).

Чтобы обойти все рёбра и вернуться в исходную вершину, нам нужно найти Эйлеров цикл. Эйлеров цикл существует в графе тогда и только тогда, когда все вершины имеют чётную степень.

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

Для того чтобы все вершины стали чётными, нужно пройти дважды такое количество рёбер, чтобы суммарная степень вершин стала чётной. Поскольку у нас 20 вершин с нечётной степенью, нам нужно