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

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

Как найти стартовую вершину, если Полина закончила в вершине 3

• Ключевой факт: траектория, проходящая по каждому ребру ровно один раз, существует только в двух случаях:

  • все вершины имеют четную степень (0 вершин нечетной степени) — траектория замкнутая (начинается и заканчивается в одной и той же вершине);
  • ровно две вершины имеют нечетную степень — траектория идет от одной нечетной вершины к другой нечетной вершине.

• Применение к условию задачи, где конец траектории — вершина 3:

  • Случай 1: все вершины имеют четные степени. Тогда траектория замкнутая, и старт совпадает с финишем. Значит, стартовая вершина тоже 3.
  • Случай 2: ровно две вершины имеют нечетную степень. Одна из них — вершина 3 (конец). Тогда стартовая вершина — другая нечетная вершина графа (то есть та вершина, у которой нечетная степень и которая не равна 3).

Как применить к конкретному рисунку (когда он будет передан):

1. Посчитайте степень каждой вершины (сколько ребер incident к ней).
2. Определите вершины с нечетной степенью.
3. Если их две и одна из них — вершина 3, то старт — это другая нечетная вершина.
4. Если их ноль, старт равен 3.

Готов разобрать конкретно ваш рисунок: пришлите изображение или перечислите степени вершин, и я скажу точно, от какой вершины Полина начинала обводить граф.