Задача
Докажите, что связный граф с 2n нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно n –1 раз и не проводя никакое ребро дважды.
Решение
Разобьём нечётные вершины на пары и каждую пару соединим новым ребром. Согласно задаче 130806 полученный граф можно обойти по циклу. Удалив новые рёбра, мы разобьём цикл на n частей.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет