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

Пошаговое решение:

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

Ответ: M или N