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

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

В данном графе четыре вершины: D, E, F, C.

Степень вершины D равна 3.

Степень вершины E равна 3.

Степень вершины F равна 3.

Степень вершины C равна 3.

Все вершины нечетные.

Если Катя начала в вершине D, то закончит она в вершине, отличной от D (E, F или C).

Так как у нас все вершины имеют степень 3, то, начав в вершине D, Катя закончит в одной из вершин: E, F или C.

На рисунке изображена схема обхода графа, начинающаяся в вершине D и заканчивающаяся в вершине F.

Ответ: F