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

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

Когда мы проведем путь по графу, начиная с вершины D (по правилам обводки без отрыва карандаша и без повторения рёбер), мы увидим, что каждая вершина будет иметь четное количество инцидентных ей рёбер, кроме начальной и конечной вершин.

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

Исходя из рисунка графа, видим, что вершины A, B, C, E имеют четное количество инцидентных рёбер, а вершина D имеет нечетное количество (3 ребра инцидентны вершине D), так как входит в обводку и выходит из нее:

 A-----B
 |     |
 |     |
 |     |
 D-----C
 |
 |
 E

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