11: На рисунке изображён граф. Аня обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Аня начала обводить граф, если она закончила его обводить в вершине E?
Ответ:
Чтобы обвести граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды (Эйлеров путь), необходимо, чтобы было не более двух вершин с нечётной степенью. В данном графе вершины A и E имеют нечетную степень (3). Следовательно, Аня начала обводить граф либо из вершины A, либо из вершины E. Так как она закончила в вершине E, значит, начала она в вершине **A**.