Ваня хочет обвести граф, изображённый на рисунке, не отрывая карандаша от лис- та бумаги и не проводя ни по одному ребру дважды. С какой вершины Ване стоит на- чать обводить граф? Ответ: A B C F E D

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

Чтобы это было возможно, необходимо, чтобы количество нечетных вершин (вершин, из которых выходит нечетное количество ребер) было либо 0, либо 2.

Считаем количество ребер, выходящих из каждой вершины:

• A: 3 ребра
• B: 3 ребра
• C: 3 ребра
• D: 2 ребра
• E: 3 ребра
• F: 2 ребра
• O: 4 ребра

Нечетные вершины: A, B, C, E. Четные вершины: D, F, O.

Так как нечетных вершин четыре, то начать Ваня может с любой из этих вершин: A, B, C, E.

Ответ: A, B, C, E