Задача 31096

Темы:    [ Степень вершины ] [ Обход графов ]

Сложность: 3+ Классы: 6,7,8

Условие

Доказать, что связный граф можно обойти, проходя по каждому ребру дважды.

Решение

Заменим каждое ребро на два, соединяющих те же вершины. Далее см. задачу 30806.

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	28