На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она закончила его обводить в вершине D?
Заметим, что степени всех вершин этого графа четны, кроме вершин A и D. Если бы она закончила не в той же вершине, где начала, то путь прошел бы по нечетному количеству ребер последней вершины (одно ребро в конце и пары входящее-исходящее ребро до этого на маршруте), Если бы, напротив, она начала его в той же вершине, то путь прошел бы по четному количеству ребер стартовой вершины, то есть не по всем (у вершин D и A нечетное число ребер). Значит, она закончила его в вершине нечетной степени (чтобы обойти все ее ребра), то есть в A или в D. В D она закончила, значит, начала в A.
Ответ: A.