Есть несколько способов раскрасить рёбра куба в шесть цветов с соблюдением условия задачи. Вот один из них:

  Покажем, что больше шести цветов быть не может.   Предположим, что мы покрасили рёбра куба в семь или более цветов. Поскольку всего у куба 12 рёбер, то должен быть цвет, например, белый, в который покрашено только одно ребро. Для каждого ребра куба есть ровно четыре ребра, соседних с ним. Значит, с белым цветом в паре может быть не больше четырёх цветов, а значит, всего различных цветов не может быть больше пяти. Противоречие.

6 цветов.