Рисунке изабражëн граф Катя оьвела этот граф не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды Начала она в вершине D В какой вершине Катя закончила обводить граф

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