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

Для решения этой задачи нам нужно применить правило об обходе графа без повторений и без отрыва карандаша. Это правило, называемое **Эйлеровым циклом**, гласит, что каждое ребро графа должно быть пройдено ровно один раз. При обходе графа появляется понятие **чётности вершин**. Вершина графа называется **чётной**, если количество инцидентных ей рёбер является чётным, и **нечётной**, если это количество нечётное. Для решения задачи также важно знать, что в графе с **2 нечётными вершинами** можно начать и закончить обход в этих вершинах. Теперь давайте применим это правило к графу, изображенному Николаем: - Посмотрим на вершину **A**, в которой Николай закончил обводить граф. Эта вершина будет иметь нечётную степень (так как он закончил в ней). - Так как каждая вершина графа имеет чётную степень, за исключением начальной и конечной вершин, то **A** должна быть нечётной. - Следовательно, **Вершина, в которой Николай начал обводить граф, должна быть также нечётной**. Таким образом, Николай начал обводить граф в **нечётной вершине**.