Задача по графам

Любой ли связный граф можно нарисовать, не отрывая карандаша от бумаги, если по каждому ребру разрешается проводить ровно два раза?

Подсказка:

Попробуй в определенном связном простом графе заменить каждое ребро на два ребра (если A и B соединены одним ребром, мы проводим между ними дополнительное ребро). Будет ли такой граф Эйлеровым?

9 симпатий

Решение выглядит следующим образом:

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

Но не до конца понимаю, для чего необходимо была замена ребер на параллельные, можете подсказать?

1 симпатия

параллельные для определенности, по идее неважно какой формы ребро (хоть контур тюленя :seal:) главное чтобы он выходил из одной вершины и заходил в другую.
То есть единственное что важно, это то что мы из одного ребра, сделали два

3 симпатии

Думаю,для ясности,ибо заменив все ребра на 2 параллельные,то мы меняем условие
У нас теперь есть граф с вершинами,у которых степени четные числа и по каждому ребру можно пройти ровно один раз(Эйлеров мост вспоминается)

2 симпатии