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

Граф является эйлеровым, если все вершины имеют четную степень. В данном графе вершины E и F имеют степень 3 (нечетную), а остальные вершины (A, B, C, D, O) имеют степень 2 (четную).

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

Так как Ваня начал в вершине F (имеющей нечетную степень), он должен закончить в другой вершине с нечетной степенью, которой является вершина E.