Почему для некоторых графов возможно обвести их не отрывая карандаша от бумаги?

Графы, которые можно нарисовать, не отрывая карандаша от бумаги, называют эйлеровыми в честь учёного Леонарда Эйлера. xn--j1ahfl.xn--p1ai

Возможность такого обвода зависит от количества нечётных вершин графа: science-start.ru

• Если все вершины чётные, то граф можно начертить, не отрывая карандаша от бумаги. science-start.ru При этом можно начинать с любой вершины графа и завершить его в той же вершине. science-start.ru
• Если ровно две вершины графа нечётные, то также возможно начертить граф, не отрывая карандаша от бумаги. science-start.ru При этом нужно начинать с одной из нечётных вершин и завершить обход в другой нечётной вершине. science-start.ru
• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. science-start.ru

Это объясняется так: когда обводят граф и пройденные рёбра выкидывают, то при прохождении через вершину её степень уменьшается на 2. mmmf.msu.ru Поэтому степени всех вершин сохраняют чётность. mmmf.msu.ru Когда обвод заканчивается, степени всех вершин должны оказаться равны нулю. mmmf.msu.ru