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

**Понимание задачи:** Марта обвела граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Значит, это задача о поиске эйлерова цикла — пути, который проходит по каждому ребру графа ровно один раз и возвращается в исходную вершину. **Решение:** 1. Чтобы определить, с какой вершины Марта начала обводить граф, необходимо рассмотреть степени вершин графа. Степень вершины - количество инцидентных ей рёбер. 2. Поскольку Марта обошла каждое ребро, потребуется, чтобы все вершины графа были чётной степени (за исключением, возможно, двух вершин, если это направленный граф). 3. Поскольку она закончила в вершине К и вершина К имеет нечётную степень, значит, Марта начала свой путь в какой-то другой вершине. 4. Это можно понять из теоремы Эйлера: граф содержит эйлеров цикл тогда и только тогда, когда у него нет вершин нечётной степени или их количество чётно и равно 2. 5. Поэтому, вершина, в которую Марта начала обводить граф, обладает нечётной степенью. Таким образом, если вершина K имеет нечётную степень и является концом цикла (последней вершиной), Марта начала обводить граф из вершины, не являющейся вершиной K.