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

Ответ: B

Разбираемся:

• Определим степени всех вершин графа:
• Степень вершины B равна 3 (нечетная).
• Степень вершины C равна 3 (нечетная).
• Степень вершины A равна 4 (четная).
• Степень вершины D равна 2 (четная).
• Степень вершины N равна 4 (четная).
• Степень вершины K равна 3 (нечетная).

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

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

Так как нужно закончить обводить граф в вершине K, то начать нужно в вершине B.

Ответ: B