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

Разбираемся:

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

Если таких вершин две, то обход начинается в одной из них и заканчивается в другой.

Если такая вершина одна, то обход начинается и заканчивается в ней.

Определим степени вершин:

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

Вершины C и F имеют нечётную степень (3). Значит, обход графа начинается в одной из этих вершин и заканчивается в другой.

Так как Ваня закончил обводить граф в вершине C, то начал он в вершине F.

Ответ: F

Проверка за 10 секунд: Нашли вершины с нечётной степенью и определили начальную вершину.