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

Анализ степеней вершин графа №2:

• A: 2 (четное)
• B: 3 (нечетное)
• C: 2 (четное)
• D: 3 (нечетное)
• E: 2 (четное)
• F: 2 (четное)
• G: 3 (нечетное)
• H: 4 (четное)
• K: 3 (нечетное)
• L: 2 (четное)
• M: 3 (нечетное)
• N: 4 (четное)
• P: 2 (четное)
• R: 4 (четное)

Решение:

В графе №2 вершины с нечетной степенью: B (3), D (3), G (3), K (3), M (3). Всего 5 вершин с нечетной степенью.

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

Однако, если предположить, что Света *смогла* обойти граф, как сказано в условии, то это означает, что граф имеет 0 или 2 вершины с нечетной степенью. Так как в приведенном графе 5 вершин с нечетной степенью, существует противоречие.

Если принять условие, что обход был выполнен, и начало было в вершине M (которая имеет нечетную степень), то конец обхода должен быть в другой вершине с нечетной степенью. Поскольку таких вершин 5 (B, D, G, K, M), и начало было в M, Света могла закончить в любой из оставшихся вершин с нечетной степенью: B, D, G, или K.

Из-за противоречия между условием (граф обойден) и реальностью (граф имеет 5 вершин с нечетной степенью), задача некорректна. Но если следовать логике