В стране 20 городов, причем между любыми двумя городами проложена дорога. Министерство путей сообщения может закрыть на ремонт любую дорогу из четырех, образующих циклический маршрут. Может ли после нескольких таких операций остаться только 19 дорог?
Подсказка
Понятно, что после каждой из указанных операций остается связный граф, а в конце должно получиться дерево.
Решение
Ответ: Нет.
Решение. Понятно, что после каждой из указанных операций остается связный граф, а в конце должно получиться дерево. Вершины дерева можно раскрасить в два цвета так, чтобы у всех его ребер были концы разных цветов. Если мы будем по очереди добавлять убранные ребра (сначала — убранное последним, потом — предпоследним и т.д.), то это свойство не нарушится (т.к. 4 — четное число). Но вершины полного графа, который по условию был в начале, так раскрасить нельзя.