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

Для того чтобы граф можно было обвести, не отрывая карандаша от бумаги и не проводя ни по одному ребру дважды (эйлеров путь), необходимо, чтобы в графе было не более двух вершин с нечётной степенью (количеством ребер, выходящих из вершины). Если таких вершин нет или две, то можно начать обход с любой из этих вершин (если они есть) и закончить в другой (если их две). Если таких вершин нет, то можно начать и закончить в одной и той же вершине. В данном графе вершины A, B, D и E имеют нечётную степень (3). Поскольку эйлеров путь может начинаться только в вершине с нечётной степенью и заканчиваться в другой вершине с нечётной степенью, а закончила Аня в вершине E, то начала она в одной из вершин A, B или D. Проверим вершины: Начнем с вершины A. Возможный путь: A-B-C-D-A-E-F-B-D-E Начнем с вершины B. Возможный путь: B-A-D-C-B-F-E-D-A-E Начнем с вершины D. Возможный путь: D-C-B-A-D-E-F-B-A-E Ответ: A, B или D