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

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

Подсчитаем степени вершин:
- A: 2
- M: 4
- N: 4
- B: 2
- P: 2
- C: 2
- K: 2

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