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

Для решения задачи необходимо определить степени вершин графа. Степень вершины - это количество ребер, инцидентных этой вершине.

Вершины графа и их степени:

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

Эйлеров путь существует в графе, если в графе не более двух вершин с нечетными степенями. В данном графе 3 вершины имеют нечетную степень: B, D, F. Следовательно, нельзя пройти по всем ребрам графа ровно один раз, не отрывая карандаш от бумаги. Но, если мысленно добавить еще одну вершину, то задачу решить можно.

По условию задачи Николай закончил обводить граф в вершине I. Следовательно, начать он мог в вершине G.

Ответ: G