(image credit: Wolfram Mathworld, http://mathworld.wolfram.com/ReidemeisterMoves.html )

Соответственно, нужно доказать, что каждое такое движение не изменяет числа трёхцветных раскрасок.

Как нас учат специалисты по комбинаторике, лучше всего равенство натуральных чисел доказывается биекцией. Так вот — между трёхцветными раскрасками есть биекция, сохраняющая раскраску вне перестраиваемой области (а легко видеть, что внутрь области перестройки раскраска всегда продолжается не более чем одним способом).

Например:

Правда, проверять такое утверждение напрямую грустно: нужно для всех возможных наборов входящих снаружи цветов проверить, что либо одновременно внутрь продолжится, либо не продолжится, и это довольно много вариантов.

Ну или нужно сказать, что при данных цветах сверху, продолжая через картинку, мы и в том, и в другом случае получим всегда одни и те же цвета снизу — что уже более разумно, но всё ещё остаётся каким-то странным перебором.

И тут помогает вот какое наблюдение: обозначим наши цвета 0, 1 и 2. Три цвета удовлетворяют условию "все одинаковые или все разные" тогда или только тогда, когда их сумма равна 0 mod 3.

Действительно, 0+1+2=0 mod 3, 3x=0 mod 3.

(А третий цвет однозначно определяется двумя, так что переход в обратную сторону тоже мгновенный)

Соответственно, мы можем работать в поле по модулю 3 — зная, что если два из подошедших к перекрёстку цветов это a и b, то третий это -(a+b).

И теперь уже мгновенно проверяется, что если три подходящих к R3-перестройке сверху (на рисунке выше) цвета это a, b и c (слева направо), то вниз они придут и в том, и в другом случае как
-a+b+c, b и -(a+b).

А проверить движения R1 и R2 ещё быстрее.

Правда, всё равно остаётся ощущение чуда: почему именно при таких правилах получился инвариант?

Оказывается, на это есть хороший ответ — но прежде ещё пара замечаний.
Во-первых, мы между делом обнаружили, что число правильных трёхцветных раскрасок всегда будет степенью тройки. Потому что это число решений системы линейных (однородных) уравнений вида x_i+x_j+x_k=0 (где i,j и k — номера нитей, встречающихся в данном перекрёстке) над полем из трёх элементов.

А это 3 в степени размерность пространства решений.

Во-вторых, условие "три одинаковых или три разных" встречается ещё в замечательной игре SET:

Там нужно находить (из выложенных на стол 12) тройки карточек, по каждому из четырёх параметров (цвет, тип закраски, количество, форма) либо все совпадающие, либо все различающиеся. И из-за перевода выше это можно переформулировать как поиск прямых в четырёхмерном пространстве над полем из трёх элементов.
Не то, чтобы это сильно в игре помогало. :)

Так вот — а _почему_ число трёхцветных раскрасок это инвариант?
Оказывается, что хоть мы на него смотрели "аддитивно", на него есть и "некоммутативный" взгляд.

У узла есть такой естественный инвариант: фундаментальная группа дополнения к нему (https://en.wikipedia.org/wiki/Knot_group )