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

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

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