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

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

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

Понятие степени вершины в графе означает количество инцидентных ей рёбер. Если вершина имеет нечетную степень, это означает, что граф в этой вершине не будет "закончен" во время обводки.

Посмотрим на процесс обводки графа: когда Петя начинает с какой-либо вершины и проходит по соединенным рёбрам, он приходит в новую вершину каждый раз, когда переходит через ребро. Учитывая, что он закончил обвод графа в вершине B, это означает, что вход и выход Пети из каждой вершины (кроме, возможно, начальной и конечной вершин) должны совпасть.

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

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