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

Решение:

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

Рассмотрим степени вершин на рисунке:

• Степень вершины A: 2
• Степень вершины B: 3
• Степень вершины C: 2
• Степень вершины D: 3
• Степень вершины E: 2
• Степень вершины F: 2

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

Однако, если мы предполагаем, что в задаче есть опечатка и закончила она в вершине B или D, тогда она начала в другой из этих вершин. Если же задание верное, и она закончила в E, это означает, что все вершины, кроме начальной и конечной, должны иметь четную степень. В данном графе вершины B и D имеют нечетную степень. Если бы она начала в B и закончила в D, то это возможно. Но она закончила в E.

Перечитав условие,