Саша хочет обвести граф, изображённый на рисунке, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Саше стоит начать обводить граф?
Степени всех вершин этого графа четны, кроме вершин A и F. Если бы Саша закончил обводку не в той же вершине, где начал, то путь прошел бы по нечетному количеству ребер последней вершины — одно ребро в конце и пары входящее-исходящее ребро до этого на маршруте. Если бы, напротив, Саша закончил обводку в той же вершине, где начал, то путь прошел бы по четному количеству ребер стартовой вершины, то есть не по всем, потому что у вершин A и F нечетное число ребер. Следовательно, Саша закончил обводку в вершине нечетной степени, чтобы обойти все ее ребра, то есть в вершине A или в вершине F. Таким образом, закончил Саша в вершине A или в вершине F.
Ответ: A или F.