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

Решение:

• В графе вершины A, C, D и N имеют нечетную степень (количество ребер, выходящих из вершины равно 3), а вершины B и K имеют четную степень (количество ребер, выходящих из вершины равно 4).
• Так как граф можно обвести, не отрывая карандаша от бумаги, и начать обводить его в вершине C, то закончить обводить граф Мария должна в другой нечетной вершине.

Ответ: N