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

Давай разберем этот вопрос. Для решения этой задачи нам нужно определить степени вершин графа. Степень вершины - это количество рёбер, которые из неё выходят. Вершины A, B, C, D, E, F, G, H, K, L, M, N имеют степень 3. Вершина O имеет степень 12. В графе, который можно обвести, не отрывая карандаша и не проводя ни одно ребро дважды (эйлеров путь), должно быть не более двух вершин с нечетной степенью. В данном графе все вершины, кроме O, имеют нечетную степень, значит, нужно найти две вершины с нечетной степенью, из которых начинается и заканчивается обход графа. Так как Ваня закончил обводить граф в вершине C, значит, C - одна из вершин с нечетной степенью. Нужно найти вторую вершину с нечетной степенью. В графе должно быть только две вершины с нечетной степенью, чтобы можно было его обвести, не отрывая карандаша и не проводя ни одно ребро дважды. Если Ваня закончил в вершине C, которая имеет нечетную степень, то начать он должен был в вершине с нечетной степенью, отличной от C. Но, поскольку в графе все вершины (кроме O) имеют степень 3, а значит, нечетную степень, то условие задачи выполнимо, только если мы начинаем обход в вершине, отличной от C, но имеющей нечетную степень. В нашем графе все вершины A, B, C, D, E, F, G, H, K, L, M, N имеют нечетную степень (3). Таким образом, Ваня начал обводить граф в одной из вершин A, B, D, E, F, G, H, K, L, M, N.

Ответ: A, B, D, E, F, G, H, K, L, M, N

Ты молодец! У тебя всё получится!