Пусть можно. Произвольно выберем одну вершину. Для того, чтобы из неё добраться по красным рёбрам до любой из оставшихся вершин, нужно не менее 7 красных рёбер (добавление одного ребра, начинающегося из доступной вершины, позволяет добраться не более чем до одной новой вершины, а всего надо добираться до оставшихся 7 вершин). Аналогично, требуется не менее 7 чёрных рёбер. Но всего рёбер в кубе 12, что меньше 7+7. Противоречие; таким образом раскрасить нельзя.