Question

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

Answer 1

Ответ :

Нельзя так покрасить ребра .

Решение :

Чтобы по ребра одного цвета можно было попасть из каждой вершины в каждую нужно , чтобы одноцветные ребра образовывали связный граф . В кубе 8 вершин , значит , в одноцветном графе будет не меньше 7 ребер . Так как таких одноцветных графа должно быть 2 , то в кубе должно быть не меньше 14 ребер , а в нем всего 12 ребер .