Пусть $ P$ знает о неизоморфизме графов $ G_1$ и $ G_2$. $ P$ хочет доказать $ V$ свое знание, не показывая само доказательство неизоморфизма.

Общий вход: пара графов $ G_0=(V,E_0)$ и $ G_1=(V,E_1)$.

1) Первый шаг проверяющего. Проверяющий $ V$ наугад с равномерным распределением вероятностей выбирает элемент $ \alpha$ из множества $ \{0,1\}$ и перестановку $ \pi$ из множества перестановок множества вершин $ V$. Далее $ V$ строит граф $ H=\pi(G_\alpha)$ с множеством вершин $ V$ и множеством ребер $ F=\{(\pi(u),\pi(v)):(u,v)\in E_\alpha\}$. (Граф $ H$ является случайной изоморфной копией либо графа $ G_1$, либо графа $ G_0$.) Граф $ H$ будет называться вопросом. Затем $ V$ строит $ n^2$ пар графов таких, что каждая пара содержит одну изоморфную копию графа $ G_1$ и одну изоморфную копию графа $ G_0$. Графы в парах расположены в случайном порядке. Эти пары будут называться тестовыми парами, они будут использоваться доказывающим для тестирования того, что не обманывает ли проверяющий. В частности, для любого $ 1\leq i\leq n^2$ проверяющий $ V$ наугад с равномерным распределением вероятностей выбирает бит $ \gamma_i$ из множества $ \{0,1\}$ и две перестановки $ \tau_{i,1}$, $ \tau_{i,0}$ из множества перестановок множества вершин $ V$, и строит для $ j \in \{0,1\}$ графы $ T_{i,j} = \tau_{i,j}(G_{j+\gamma_i mod2})$. Проверяющий $ V$ отправляет граф $ H$ и последовательность пар $ (T_{1,1},T_{1,0})$, ..., $ (T_{n^2,1},T_{n^2,0})$ доказывающему $ P$.

2) Первый шаг доказывающего. Доказывающий $ P$ наугад выбирает подмножество $ I\subseteq\{1,2,...,n^2\}$. ($ I$ выбирается наугад с равномерным распределением вероятностей из множества всех $ 2^{n^2}$ подмножеств.) $ P$ отправляет $ I$ проверяющему $ V$.

3) Второй шаг проверяющего. Если $ I$ не является подмножеством $ \{1,2,...,n^2\}$, то $ V$ прекращает проверку и отвергает доказательство. В противном случае, $ V$ отвечает с $ \{(\gamma_i,\tau_{i,1},\tau_{i,0}):i \in I\}$ и $ \{(\alpha+\gamma_{i}mod2, \tau_{i,(\alpha+\gamma_{i}mod2)}\pi^{-1}):i \in \bar I \}$, где $ \bar I =\{1,2,...,n^2\}-I$. Т.е. для $ i \in I$ $ V$ показывает изоморфизм между входными графами и $ i$-ой парой, а для $ i \in \bar I$ $ V$ показывает изоморфизм между графом $ H$ и одним из графов из $ i$-ой пары. Интуитивно, для $ i \in I$ $ V$ показывает, что $ i$-ая пара правильно построена, а для $ i \in \bar I$ $ V$ показывает, что если $ i$-ая пара правильно построена, то граф $ H$ также правильно построен.

4) Второй шаг доказывающего. $ P$ проверяет является ли $ \tau_{i,j}$ действительно изоморфизмом между $ T_{i,j}$ и $ G_{(j+\gamma_i mod2)}$ для всех $ i \in I$ и $ j \in \{0,1\}$ и является ли $ \tau_{i,(\alpha+\gamma_{i}mod2)}\pi^{-1}$ действительно изоморфизмом между $ T_{i,(\alpha+\gamma_{i}mod2)}$ и $ H$ для всех $ i \in \bar I$. Если одно из этих условий нарушается, $ P$ останавливается. В противном случае, $ P$ отвечает с $ \beta \in \{0,1\}$ таким, что $ H$ изоморфен $ G_\beta$. (Если такого $ \beta$ не существует, то $ P$ отвечает с $ \beta=0$.)

5) Третий шаг проверяющего. Проверяющий $ V$ тестирует верно ли, что $ \alpha=\beta$. Если это условие нарушается, $ V$ останавливается и отвергает доказательство. В противном случае, $ V$ продолжает.

6) $ P$ и $ V$ повторяют шаги 1) - 5) $ m$ раз, каждый раз используя независимые случайные подбрасывания монеты.

7) Заключительный шаг проверяющего. Проверяющий принимает доказательство, если он завершит $ m$ итераций шагов 1) - 5). В противном случае, отвергает.