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

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

Посмотрим на степени вершин данного графа:

• A: 2
• B: 2
• C: 4
• D: 3
• E: 4
• F: 2
• G: 3

У вершин D и G нечетная степень (3). Значит, обход графа должен начинаться в одной из этих вершин и заканчиваться в другой. Поскольку обход заканчивается в вершине G, то начинаться он должен в вершине D.

Ответ: D