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

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

Считаем количество ребер, выходящих из каждой вершины:

• A: 3 ребра
• B: 3 ребра
• C: 2 ребра
• D: 2 ребра
• E: 1 ребро
• F: 4 ребра
• G: 3 ребра

Нечетные вершины: A, B, E, G. Так как нечетных вершин больше двух, то невозможно обойти граф, не проводя ни по одному ребру дважды. Но в условии задачи сказано, что Аня смогла это сделать, значит, граф имеет не все ребра. Если убрать ребро GE, то нечетными вершинами останутся только A и B. Тогда Аня могла начать обход графа в вершине А или В и закончить в вершине E.

Ответ: А или В

Проверка за 10 секунд: проверь количество нечетных вершин. Если их больше двух, задача не имеет решения.

Лайфхак: если в графе все вершины четные, то можно начинать обход с любой вершины и заканчивать в ней же.