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

Ответ: E

Решение:

• Граф можно обвести, не отрывая карандаша и не проводя ни по одному ребру дважды, только если степени всех вершин четные, либо есть ровно две вершины с нечетной степенью (начальная и конечная).
• В данном графе вершины A, C, D, E и F имеют степень 3 (нечетные), а вершина B имеет степень 4 (четная).
• Так как у нас больше двух вершин с нечетной степенью, надо найти другой способ обхода графа. Заметим, что можно добавить ребро между двумя вершинами с нечетной степенью, чтобы все вершины стали четными.
• Если Лева закончил обход в вершине C, то начать он мог в вершине E.

Ответ: E