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

Решение:

В графе, который можно обойти одним росчерком (не отрывая карандаша и не проводя ребро дважды), может быть либо 0, либо 2 вершины с нечётным числом рёбер (степень вершины).

• Если все вершины имеют чётную степень, то начать и закончить обход можно в любой вершине.
• Если есть две вершины с нечётной степенью, то начать обход нужно в одной из них, а закончить — в другой.

Посчитаем степени вершин на рисунке:

• A: 2
• B: 4
• C: 4
• D: 4
• E: 2
• F: 4
• G: 2
• H: 2
• K: 2
• L: 2
• M: 2
• N: 2

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

Ответ: E (или любая другая вершина)