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

Анализируем граф. Марта закончила обводить граф в вершине A. Это означает, что в вершине A сходится нечетное количество ребер.

Подсчитаем количество ребер, сходящихся в каждой вершине:

• A: 3 ребра
• B: 4 ребра
• C: 4 ребра
• D: 4 ребра
• E: 2 ребра

Так как Марта начала обводить граф в некоторой вершине, и закончила в вершине A, то она должна была начать в вершине с нечетным количеством ребер, отличной от A. В данном графе только вершина A имеет нечетное количество ребер (3). Это означает, что Марта должна была начать в вершине A, чтобы закончить в вершине A.

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

Из условия следует, что Марта начала обводить граф в одной из вершин и закончила в вершине А. Значит, необходимо найти вершину, из которой можно начать обход графа, чтобы закончить в вершине А, не проводя ни одно ребро дважды.

Так как в вершине A сходится 3 ребра, значит, Марта могла начать в вершине D.

Ответ: D