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

Пошаговое решение:

• Степень вершины 1: 3
• Степень вершины 2: 3
• Степень вершины 3: 3
• Степень вершины 4: 3
• Степень вершины 5: 3
• Степень вершины 6: 5

Так как у нас должно быть только две вершины с нечетной степенью, а все остальные с четной, значит, в данном графе есть ошибка. Проверим количество ребер, выходящих из каждой вершины. С учетом, что Полина начала обводить граф из вершины, степень которой 5, она закончила обводить граф в вершине 3.

• Количество ребер, выходящих из вершины 3: 3

Значит, Полина начала обводить граф из вершины 6.