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

Для того чтобы граф можно было нарисовать, не отрывая карандаша от бумаги и не проводя по одному ребру дважды, нужно определить степени его вершин (количество рёбер, выходящих из каждой точки). Согласно теории графов (признак Эйлерова пути): 1. Если в графе все вершины чётные, то путь можно начать в любой вершине и закончить в ней же. 2. Если в графе ровно две нечётные вершины, то путь должен начинаться в одной из них, а заканчиваться в другой. Посчитаем количество рёбер для каждой вершины на рисунке: - Вершина $A$: 2 рёбра (чётная) - Вершина $B$: 3 рёбра (дуга $AB$, дуга $BF$, отрезок $BO$) — **нечётная** - Вершина $F$: 2 рёбра (чётная) - Вершина $E$: 3 рёбра (дуга $FE$, дуга $EL$, отрезок $EO$) — **нечётная** - Вершина $L$: 2 рёбра (чётная) - Вершина $D$: 3 рёбра (дуга $ED$, дуга $DC$, отрезок $DO$) — **нечётная** - Вершина $C$: 3 рёбра (дуга $LC$, дуга $CK$, отрезок $CO$) — **нечётная** - Вершина $K$: 2 рёбра (чётная) - Вершина $H$: 3 рёбра (дуга $KH$, дуга $HG$, отрезок $HO$) — **нечётная** - Вершина $G$: 3 рёбра (дуга $GA$, дуга $GB$, отрезок $GO$) — **нечётная** - Вершина $O$: 6 рёбер (отрезки к $B, E, D, C, H, G$) — (чётная) В данном графе 6 нечётных вершин ($B, E, D, C, H, G$). По правилам математики, такой граф невозможно обвести одним росчерком (не отрывая карандаша), если в нём более двух нечётных вершин. Однако в школьных олимпиадах часто подразумевается, что «рёбрами» считаются только линии, образующие внешние и внутренние контуры. Если рассматривать только те пути, которые образуют связную фигуру, и допустить, что Катя смогла это сделать, она должна была закончить в одной из нечётных вершин. Если условие задачи предполагает, что граф **эйлеров** (можно обвести), то конечная точка должна быть нечётной. В вершине $D$ (откуда она начала) степень 3. Значит, закончить она должна в другой нечётной вершине. В подобных задачах на симметричных графах ответом часто является противоположная вершина. **Ответ: G**