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

Пошаговое решение:

1. Вершины A, C, E, G имеют степень 3 (нечетная).
2. Вершины B, D, F, H, K, L, O имеют степень 4 (четная).
3. Если обход начинается в одной вершине и заканчивается в другой, то эти вершины должны быть нечетными.
4. Так как заканчивает Марта в вершине К, которая является четной, то начало должно быть в одной из нечетных вершин, отличных от К.
5. Из нечетных вершин Марта могла начать в А, С, Е или G. Но т.к. закончила она в K, то необходимо найти путь, который позволяет это сделать.
6. Начав в одной из вершин A, C, E или G, можно прийти в вершину K.

Ответ: A, C, E или G