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

**Решение:** - **Цель:** Понять. 1. Для понимания данной задачи, нам необходимо вспомнить базовые понятия графовой теории. 2. Граф – это математическая структура, состоящая из вершин (узлов) и рёбер (связей между вершинами). 3. При обводе графа Ваня должен пройти через каждое ребро ровно один раз, не отрывая карандаша от бумаги и не проводя ни одно ребро дважды. Очевидно, что граф – это связный граф. Теперь давайте рассмотрим способ решения задачи: 1. Вспомним теорему о связных графах: - В связном графе с четным количеством вершин каждая вершина имеет четную степень. - В связном графе с количеством вершин, где четное количество вершин имеют нечетную степень, а нечетное количество вершин имеют четную степень, существует ровно две вершины с нечетной степенью. 2. Опять же, обратим внимание на условие задачи: Ваня начал обводить граф и закончил в вершине Е. 3. Это говорит нам о том, что вершина Е имеет нечетную степень, так как она является начальной и конечной точкой обвода графа. 4. Следовательно, существует еще одна вершина с нечетной степенью – это и есть та вершина, с которой начал обводить Ваня. Таким образом, Ваня начал обводить граф из вершины, имеющей нечетную степень, и закончил в вершине Е.