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

Ответ: 4

Логика такая:

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

В данном графе:

• Вершина 1: степень 2
• Вершина 2: степень 3
• Вершина 3: степень 2
• Вершина 4: степень 5
• Вершина 5: степень 2
• Вершина 6: степень 2
• Вершина 7: степень 2

Нечётные степени имеют вершины 2 и 4.

Так как Аня закончила обводить граф в вершине 7, то начинать она могла в вершине 4.

Ответ: 4