Любой ли связный граф можно нарисовать, не отрывая карандаша от бумаги, если по каждому ребру разрешается проводить ровно два раза?
Подсказка:
Попробуй в определенном связном простом графе заменить каждое ребро на два ребра (если A и B соединены одним ребром, мы проводим между ними дополнительное ребро). Будет ли такой граф Эйлеровым?
9 симпатий
Решение выглядит следующим образом:
Заменим каждое ребро двумя параллельными. Тогда степень каждой вершины удвоится и станет чётным числом. Кроме того, в середину одного из двух параллельных рёбер поместим новую вершину. Мы получим граф, у которого все вершины чётные: такой граф можно нарисовать, проводя по каждому ребру ровно один раз.
Но не до конца понимаю, для чего необходимо была замена ребер на параллельные, можете подсказать?
1 симпатия
параллельные для определенности, по идее неважно какой формы ребро (хоть контур тюленя 
) главное чтобы он выходил из одной вершины и заходил в другую.
То есть единственное что важно, это то что мы из одного ребра, сделали два
3 симпатии
Думаю,для ясности,ибо заменив все ребра на 2 параллельные,то мы меняем условие
У нас теперь есть граф с вершинами,у которых степени четные числа и по каждому ребру можно пройти ровно один раз(Эйлеров мост вспоминается)
2 симпатии