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

Чтобы решить эту задачу, нужно понять, что граф, который можно обвести, не отрывая карандаша и не проводя ни одно ребро дважды, должен иметь либо 0, либо 2 вершины с нечётной степенью (количеством рёбер, выходящих из вершины). В данном графе, вершины A, E, F, H, D, и B имеют степень 3, вершина K имеет степень 1, а вершины G, C, и L имеют степень 2. Так как Марта закончила в вершине K (степень 1), она должна была начать в другой вершине с нечётной степенью. Из условия мы знаем, что Марта закончила в вершине K, значит, она начала обводить граф с одной из вершин с нечётной степенью. Это вершины A, B, D, E, F, H. Если Марта начала в вершине K, она должна закончить в одной из вершин A, B, D, E, F, H. Так как Марта закончила в вершине K, то она не могла начать с вершины K. Таким образом, остается проверить вершины A, B, D, E, F, H. После осмотра графа, можно сделать вывод, что Марта начала обводить граф из вершины E. Ответ: E