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

Решение:

Согласно теореме Эйлера о прохождении графа, обход графа без отрыва карандаша и без повторного прохождения рёбер возможен тогда и только тогда, когда граф имеет 0 или 2 вершины с нечётной степенью. Если граф начинается и заканчивается в разных вершинах, то эти вершины должны иметь нечётную степень. В данном графе вершины B, D, E имеют нечётную степень (3), а вершины A, C имеют чётную степень (4). Поскольку Аня начала обводить граф в одной вершине и закончила в другой (E), то начало обхода должно быть в одной из вершин с нечётной степенью (B или D).

Ответ: B.