Сделаем вот что: пусть X выберет случайным образом одну из 6 перестановок цветов (ведь если перекрасить все красные вершины в зелёный, а все зелёные в красный — правильная раскраска останется правильной). И положит у каждой вершины запечатанный конверт с цветом получившейся правильной раскраски.

Теперь проверяющий Y выберет две соседние вершины. И вскроет соответствующие им конверты (все остальные конверты немедленно сжигаются).

Дальше может быть одно из двух:
1) Если Y обнаружил совпадающие цвета, то он говорит X "ах ты нехороший человек, обмануть хотел? Не прокатило!". На этом протокол прекращается, а X объявляется жуликом.
2) Если цвета разные, то процедура повторяется. X выбирает новую случайную перестановку, раскладывает конверты, Y выбирает две соседние вершины, вскрывает конверты в них, и так далее.

При этом — если X играет честно и выбирает каждый раз равномерно случайную перестановку, то никакой информации о раскраске (кроме того, что она, похоже, правильная) Y не получает: любая пара соседних вершин может быть равновероятно окрашена любым из 6 способов.

Наоборот, если Y выбирает проверяемое ребро случайным образом, то шанс поймать X, если он жульничает — по меньшей мере 1/N, где N — число рёбер в графе. За 100N раундов шанс, что на самом деле не знающий раскраски обманщик не будет пойман, становится меньше
(1- 1/N)^{100N} ~ e^{-100} < 10^{-40}.
(Ну и, естественно, такая вероятность может быть сделана сколь угодно малой, если 10^{-40} нам почему-то недостаточно.)