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

Решение:

Для того чтобы граф можно было обвести одним росчерком, необходимо, чтобы в нем было не более двух вершин с нечетной степенью (количеством ребер, выходящих из вершины). Если таких вершин нет или их две, то обход можно начать с любой вершины. Если же вершин с нечетной степенью больше двух, то обвести граф одним росчерком невозможно.

В данном графе вершины А и Р имеют степень 3, вершины В и С имеют степень 4, а вершины Д и Е имеют степень 2. Так как только две вершины (А и Р) имеют нечетную степень, то можно начать обход с любой из этих вершин.

Ответ: С вершины А или Р.