5. Какой из графов, изображённых на рисунках 16—18, содержит эйлеров цикл? Найдите в нём эйлеров цикл и перечислите номера вершин в порядке прохождения по циклу.

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

На рисунке 16 степени вершин 1 и 4 нечётные, поэтому эйлерова цикла нет. На рисунке 17 нечётные степени имеют вершины 1 и 3, поэтому эйлерова цикла нет. На рисунке 18 все вершины имеют чётные степени, значит, эйлеров цикл существует.

Один такой цикл: 1–2–3–4–5–3–1–6–7–1.

Каждое ребро графа 18 в этом обходе пройдено ровно один раз.

Ответ: граф на рисунке 18; цикл 1–2–3–4–5–3–1–6–7–1.