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

Для того чтобы обвести граф, изображенный на рисунке, Саше следует начать с вершины, у которой нечетная степень.

Обратим внимание на граф и вычислим степени каждой из вершин:

• Вершина A имеет степень 4
• Вершина B имеет степень 3
• Вершина C имеет степень 2
• Вершина D имеет степень 3
• Вершина E имеет степень 2

Таким образом, у вершин B и D нечетные степени. При начале обвода графа с любой из вершин с нечетной степенью, Саша сможет обвести граф, не повторяя ни одно ребро дважды.

Таким образом, Саше стоит начинать обводить граф либо с вершины B, либо с вершины D.