Упр.76 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 76. Можно ли раскрасить рёбра куба в красный и зелёный цвета так, чтобы муравей мог пройти из любой вершину в любую только по красным рёбрам, а жук — только по зелёным?

Рассмотрим куб как граф: его вершины — это 8 вершин куба, а рёбра — его 12 рёбер. Если муравей должен пройти из любой вершины в любую только по красным рёбрам, то красные рёбра должны образовывать связный граф на всех 8 вершинах. Аналогично, зелёные рёбра тоже должны образовывать связный граф на всех вершинах.

Но у куба каждая вершина имеет степень $$3$$, то есть из каждой вершины выходит ровно три ребра. Если раскрасить все рёбра в два цвета так, чтобы оба цвета давали связность, то в каждом цвете у каждой вершины должна быть хотя бы одна инцидентная ей ребро этого цвета. Тогда в каждой вершине должно быть не менее двух рёбер разных цветов, а значит, при степени $$3$$ один из цветов обязательно будет встречаться не более чем на одном ребре у вершины.

Однако для связности каждого цветного подграфа этого недостаточно: в кубе невозможно разбить все рёбра на два связных подграфа так, чтобы оба охватывали все вершины. Действительно, если бы это было возможно, то каждый из цветных подграфов содержал бы хотя бы $$7$$ рёбер, а всего рёбер у куба только $$12$$. Тогда суммарно потребовалось бы не менее $$14$$ рёбер, что невозможно.

Следовательно, такую раскраску выполнить нельзя.

Ответ

Нет, нельзя.