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

Для того чтобы определить, в какой вершине Катя закончила обводить граф, нужно посмотреть на количество ребер, сходящихся в каждой вершине. Если количество ребер, сходящихся в вершине, четное, то эта вершина может быть как промежуточной, так и конечной. Если количество ребер, сходящихся в вершине, нечетное, то эта вершина должна быть либо началом, либо концом обхода. В нашем графе: * Вершина A: 1 ребро (нечетное) * Вершина B: 1 ребро (нечетное) * Вершина C: 2 ребра (четное) * Вершина D: 3 ребра (нечетное, начало) * Вершина E: 2 ребра (четное) * Вершина F: 1 ребро (нечетное) Начало в вершине D. Должно быть еще три вершины с нечетным количеством ребер. Это вершины A, B, и F. Соответственно, Катя могла закончить обход в любой из этих вершин. Судя по направлению стрелок, Катя закончила обводить граф в вершине F.