На рисунке изображён граф. Сергей обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. В какой вершине Сергей завершил обводить граф, если начал обводить его в вершине А?

• Определим степени каждой вершины графа:
• Вершина A имеет степень 3 (нечетная).
• Вершина B имеет степень 3 (нечетная).
• Вершина C имеет степень 2 (четная).
• Вершина D имеет степень 4 (четная).
• Вершина K имеет степень 2 (четная).
• Вершина N имеет степень 4 (четная).

В данном графе всего две нечетные вершины: A и B. Это значит, что начать обход нужно с вершины A (как указано в условии), а закончить в вершине B.

Рассмотрим, как можно обойти граф, начиная с вершины A, не отрывая карандаша и не проходя по одному ребру дважды:

• A → C → N → D → A
• D → N → B → K → D
• B → K

При этом мы можем обойти граф, начиная с A и заканчивая в K.