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

В вершинах сходятся по три ребра, поэтому входов-выходов должно быть не менее четырёх. 1 Каждой паре выход-вход соответствует одно ребро, а потому необходимо не менее 16 проходов по рёбрам. 1 Таким образом, пройдены дважды будут минимум 4 ребра. 1

Также существует понятие эйлерова графа, в котором можно обойти все вершины и при этом пройти одно ребро только один раз. 4 В таком графе каждая вершина должна иметь только чётное число рёбер. 4