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

Решение:

Когда Николай обводил граф, он не отрывал карандаша от бумаги и не проходил по ребру дважды. Это означает, что на каждой вершине графа, кроме, возможно, начальной и конечной вершин, должно быть четное количество инцидентных рёбер (рёбер, инцидентных данной вершине).

Так как вершина M является конечной точкой обвода графа, она должна иметь нечётную степень (нечётное количество инцидентных рёбер) в связи с последним ребром обвода.

Следовательно, Николаю необходимо было начать с вершины, у которой нечётная степень.