На рисунке изображён граф. Оля обвела этот граф, не отры не проводя ни по одному ребру дважды. Укажите вершины обводить граф.

Ответ: B и K

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

• Вершина A имеет степень 2.
• Вершина B имеет степень 3.
• Вершина C имеет степень 4.
• Вершина D имеет степень 2.
• Вершина K имеет степень 3.
• Вершина M имеет степень 2.
• Вершина N имеет степень 2.
• Вершина P имеет степень 2.

Так как всего две вершины (B и K) имеют нечетную степень (3), то граф можно обвести, начав с одной из этих вершин и закончив в другой. Следовательно, можно начать обводить граф с вершин B и K.

Ответ: B и K