Задание 10. Есть ли в графах, изображённых на рисунках, эйлеров путь? А) да или нет; Б) да или нет.

Эйлеров путь проходит по каждому ребру ровно один раз. В связном графе он существует, если нечётную степень имеют ровно 0 или 2 вершины.

А) Нет. В каждой из пяти вершин степень 2, а граф связен: все вершины имеют чётную степень, поэтому существует эйлеров цикл, но эйлерова пути, который не является циклом, нет. (Если под эйлеровым путём понимать также замкнутый маршрут, ответ для А — да: эйлеров цикл является таким путём.)

Б) Да. Граф связен, и ровно две вершины нечётной степени: верхняя левая и нижняя правая имеют степень 3. Следовательно, существует эйлеров путь, начинающийся в одной из них и заканчивающийся в другой.