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

Для решения данной задачи мы можем воспользоваться правилом о нечетных степенях вершин. 1. Вершина графа увеличивает свою степень на 2 каждый раз, когда через нее проходит ребро. Чтобы обвести весь граф, каждая вершина, кроме начальной и конечной, должна иметь четную степень. 2. Так как граф является связным (есть путь между любой парой вершин), все вершины этого графа должны иметь степень, кратную двум, за исключением начальной и конечной вершин. 3. Исходя из правила нечетных степеней вершин, для графа, который нарисовал Пётр, возможны два варианта: - Пётр начал обводить граф из вершины 1 или 3, так как они имеют нечетные степени (3 и 1 соответственно). - Пётр мог начать обводить граф из вершины 1, так как каждая вершина графа, кроме начальной и конечной, должна иметь четную степень. 4. Исходя из того, что Пётр закончил обводить граф в вершине 6, оптимальным выбором будет вершина 1. Таким образом, можно предположить, что Пётр начал обводить граф, начиная с вершины 1.