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

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