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

Для решения этой задачи нужно понять, какие вершины графа имеют нечетную степень (то есть, из них выходит нечетное количество ребер). В графе, который можно нарисовать, не отрывая карандаша от бумаги и не проходя по одному ребру дважды, должно быть не более двух вершин с нечетной степенью. Если таких вершин нет или две, то можно начать обводку в одной из них и закончить в другой (если их две) или начать и закончить в одной и той же вершине (если таких вершин нет). Подсчитаем степени вершин графа: - A: 2 - B: 3 - C: 2 - D: 3 - E: 4 - F: 3 - M: 2 - K: 3 - N: 2 - P: 1 У нас есть 4 вершины с нечетной степенью: B, D, F, K и P, а также M, где он заканчивает. Но по условию задачи, должно быть не более двух вершин с нечетной степенью. Граф невозможно пройти, соблюдая условия задачи, так как он имеет больше двух вершин с нечетной степенью. Здесь либо ошибка в условии задачи, либо в графе. Предположим, что можно было бы пройти граф, если бы было ровно две вершины с нечетной степенью. В таком случае, Николай начал бы обводить граф в вершине P, так как он закончил в вершине M. Однако, это невозможно, потому что у нас больше двух вершин с нечетной степенью. Таким образом, Николай начал обводить граф в вершине P, но пройти по графу, соблюдая все условия, невозможно.