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

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

• Определим степени каждой вершины графа:
• K: 3
• D: 3
• B: 3
• F: 3
• N: 2
• A: 4
• C: 2
• Считаем количество нечетных вершин: K, D, B, F. Их 4.
• Так как нечетных вершин 4, то, чтобы обойти граф, нужно начать в одной нечетной вершине и закончить в другой.
• Перебираем варианты:

1. K-D-B-F-N-A-C-K-A-D-F-A-B: Заканчиваем в вершине B. Не подходит.
2. K-C-A-N-F-B-D-K-D-A-F-B-A: Заканчиваем в вершине A. Не подходит.
3. K-D-F-N-A-C-K-A-B-F-D-B-A: Заканчиваем в вершине A. Не подходит.
4. K-C-A-B-D-K-D-F-N-A-F-B-A: Заканчиваем в вершине A. Не подходит.
5. K-D-B-F-N-A-C-K-A-F-D-B-A: Заканчиваем в вершине A. Не подходит.
6. K-A-C-K-D-B-F-A-N-F-D-B-A: Заканчиваем в вершине A. Не подходит.
7. K-A-B-D-K-C-A-F-B-D-F-N-A: Заканчиваем в вершине A. Не подходит.
8. K-C-A-F-N-B-D-K-A-B-F-D-A: Заканчиваем в вершине A. Не подходит.
9. K-A-B-F-D-K-C-A-N-F-D-B-A: Заканчиваем в вершине A. Не подходит.
10. K-A-B-D-F-N-A-C-K-D-F-B-A: Заканчиваем в вершине A. Не подходит.
11. K-C-A-B-D-K-D-F-B-F-N-A: Заканчиваем в вершине N. Подходит.