Ответ:

Решение:

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

Подсчитаем степень каждой вершины (количество ребер, исходящих из нее):

  • Степень вершины А: 2 (нечетная)
  • Степень вершины B: 2 (четная)
  • Степень вершины C: 2 (четная)
  • Степень вершины D: 3 (нечетная)
  • Степень вершины E: 2 (четная)
  • Степень вершины F: 2 (четная)
  • Степень вершины O: 4 (четная)

В графе две вершины с нечетной степенью: А и D.

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

Ответ: А