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

Решение:

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

Рассмотрим степени вершин на данном графе:

• A: степень 3 (нечётная)
• B: степень 2 (чётная)
• C: степень 2 (чётная)
• K: степень 2 (чётная)
• M: степень 3 (нечётная)
• N: степень 3 (нечётная)
• P: степень 3 (нечётная)

Граф имеет четыре вершины нечётной степени (A, M, N, P). Такой граф нельзя обойти по условиям задачи.

Однако, если предположить, что на рисунке изображены не все рёбра, или что граф является несколько упрощенным представлением, то следует отметить, что обход такого графа (если бы он был возможен) начался бы в одной из вершин нечётной степени и закончился в другой. Если Петя закончил обход в вершине М (которая имеет нечётную степень), то он должен был начать обход в другой вершине нечётной степени. Среди вершин A, N, P, одна из них должна быть начальной.

Для данного графа, с четырьмя вершинами нечетной степени, невозможно выполнить обход по условию задачи. Если предположить, что задача имеет решение, и М - конечная вершина нечетной степени, то начальной должна быть одна из вершин нечетной степени: A, N, или P.