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

Краткая задача: минимальное число рёбер, которые нужно пройти дважды, чтобы обойти все рёбра куба (12 рёбер). Пояснение по шагам 1) Свойство эйлерова пути - Чтобы пройти каждое ребро ровно один раз (существовал бы эйлеров путь), у графа должны быть либо все вершины четной степени (для цикла), либо ровно две вершины нечётной степени (для пути между ними). - В кубе каждая вершина соединена с тремя ребрами, то есть степень каждой вершины равна 3 (нечётная). Всего нечётных вершин 8. Значит эйлерового пути, который проходит по каждому ребру ровно один раз, в кубе нет. 2) Нужно дублировать ребра - Чтобы сделать обход всех рёбер возможным без пропусков, придётся дублировать некоторые рёбра. Дублирование ребра увеличивает степень его концов на 1, т. е. меняет их парность. - Чтобы все вершины стали чётными, нужно выбрать пару нечётных вершин и задублировать между ними некоторый путь; этот путь увеличивает степень концов на 1 и превращает их в четные. Однако за каждое дублированное ребро пара нечётных вершин может быть исправлена только двумя их концами. 3) Нижняя граница - Всего нечётных вершин 8. Каждое дублированное ребро может «поправить» парность максимум двум вершинам (его концам). - Значит минимальное число дублированных рёбер не может быть меньше 8/2 = 4. 4) Доказательство достижимости (пример) - Куб можно разбить на 4 пары рёбер, образующих идеальный парный набор (переборка вершин по парам, чтобы пары рёбр были соседями по кубу). Пример такого набора дублируемых рёбер: - соединяем вдоль оси x: (0,0,0)–(1,0,0) - (0,1,0)–(1,1,0) - (0,0,1)–(1,0,1) - (0,1,1)–(1,1,1) Эти четыре ребра не пересекаются и покрывают все 8 вершин. - Дублируя именно эти 4 ребра, степени всех вершин станут 4 (чётные), и по существующей схеме можно пройти по всем рёбрам, используя каждое из них ровно один раз и эти 4 дублированных ребра — по второму разу. - Таким образом, существует обход всех рёбер, в котором ровно 4 ребра проходят дважды. Вывод - Минимальное число рёбер, которые нужно пройти дважды, равно 4. Дополнительно - Общая длина такого обхода составит 12 исходных рёбер plus 4 дублированных = 16 проходов по рёбрам.