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

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться теоремой Эйлера:

Если в графе все вершины имеют четную степень, за исключением возможно двух, то существует эйлеров цикл.

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

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