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

Для решения этой задачи можно воспользоваться понятием степени вершины. По условию известно, что Катя начала обводить граф в вершине C. В неориентированном графе степень вершины равна количеству инцидентных ей рёбер. Важным наблюдением является то, что если у вершины нечётная степень, то такая вершина обязательно будет начальной и конечной точкой пути. В то же время, чётная степень позволяет пройти через вершину как начать, так и закончить путь в ней, не нарушая условий задачи Кати. Таким образом, чтобы понять, где Катя закончила обводить граф, необходимо найти вершину с нечётной степенью. Посмотрим на степени вершин графа: - Вершина A: степень 3 - Вершина B: степень 4 - Вершина C: степень 4 - Вершина D: степень 3 - Вершина E: степень 2 Таким образом, у вершин A, C и D нечётные степени. Но так как Катя начала в вершине C, а это начало и конец пути, значит, она закончила обводить граф в вершине C. Итак, Катя закончила обводить граф в вершине C.