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

У куба 8 вершин. Чтобы по рёбрам одного цвета можно было попасть из любой вершины в любую, рёбра этого цвета должны образовывать связный граф. Для связности 8 вершин нужно не менее 7 рёбер.

Значит, красных рёбер должно быть не менее 7 и зелёных — тоже не менее 7. Но у куба всего 12 рёбер, а \(7 + 7 = 14 > 12\).

Ответ: нет, так раскрасить рёбра нельзя.