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

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

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

Считаем степени вершин графа:

• A - 3
• B - 3
• C - 3
• D - 3
• K - 4
• L - 2
• M - 2
• N - 2
• P - 2
• Q - 2
• R - 2

Всего четыре вершины с нечетной степенью (A, B, C, D). Значит, начать можно с любой из вершин A, B, C или D.

Ответ: A, B, C, D