2. На рисунке изображён граф. Оля обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. Укажите вершины, с которых Оля могла начать обводить граф.

Решение:

Чтобы иметь возможность обвести граф, не отрывая карандаша и не проводя ни по одному ребру дважды, граф должен иметь либо 0, либо 2 вершины с нечётным числом рёбер (нечётных вершин).

Давайте определим степень каждой вершины на данном графе:

• Вершина A: 3 ребра (3-A, A-D2, A-M) → нечётная степень.
• Вершина B: 4 ребра (B-A, B-C, B-M, B-E) → чётная степень.
• Вершина C: 4 ребра (C-B, C-D2, C-E, C-N) → чётная степень.
• Вершина D2: 3 ребра (D2-A, D2-C, D2-N) → нечётная степень.
• Вершина E: 4 ребра (E-B, E-C, E-M, E-N) → чётная степень.
• Вершина M: 4 ребра (M-A, M-B, M-E, M-N) → чётная степень.
• Вершина N: 4 ребра (N-C, N-D2, N-E, N-M) → чётная степень.

В данном графе две вершины с нечётной степенью: A (3) и D2 (3).

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

Следовательно, Оля могла начать обводить граф с вершин A или D2.

Ответ: A, D2.