Задача 31095

Темы:    [ Степень вершины ] [ Обход графов ] [ Четность и нечетность ] [ Деревья ] [ Индукция (прочее) ]

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

Условие

а) В графе есть эйлеров путь. Доказать, что граф связен и вершин с нечётной степенью в нём не больше двух.
б) Доказать обратное: если в связном графе вершин с нечётной степенью не больше двух, то в нём есть эйлеров путь.

Решение

  a) Каждая нечётная вершина является либо началом, либо концом пути.

  б) См. задачу 30806.

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

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