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

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