Общий вход: пара графов $ G_1=(V_1,E_1)$ и $ G_2=(V_2,E_2)$. Пусть $ \varphi$ - изоморфизм между $ G_1$ и $ G_2$, т.е. биективное отображение множества вершин $ V_1$ на множество вершин $ V_2$ такое, что $ (u,v)\in E_1$ тогда и только тогда, когда $ (\varphi(u),\varphi(v))\in E_2$.

1) Первый шаг доказывающего. Доказывающий $ P$ выбирает случайную изоморфную копию графа $ G_2$ и отправляет её проверяющему $ V$. Т.е доказывающий выбирает наугад перестановку $ \pi$ из множества перестановок множества вершин $ V_2$ и строит граф с множеством вершин $ V_2$ и множеством ребер

$\displaystyle F=\{(\pi(u),\pi(v)):(u,v)\in E_2\}.$

Доказывающий отправляет $ (V_2,F)$ проверяющему.

Примечание. Если входные графы изоморфны, как утверждает доказывающий, то граф, отправленный на первом шаге изоморфен обоим входным графам. А если входные графы не изоморфны, то никакой граф не может быть изоморфным обоим входным графам.

2) Первый шаг проверяющего. После получения графа $ G'=(V', E')$ от доказывающего, проверяющий просит доказывающего показать изоморфизм между $ G'$ и одним из входных графов, выбранным наугад проверяющим. А именно, проверяющий равномерно выбирает $ \sigma\in\{1,2\}$ и отправляет его доказывающему (который должен показать изоморфизм между $ G_\sigma$ и $ G'$).

3) Второй шаг доказывающего. Если сообщение, полученное от проверяющего, равно 2, то доказывающий отправляет $ \pi$ проверяющему. В противном случае (т.е. если $ \sigma\neq 2$) доказывающий отправляет $ \pi\circ\varphi$ (т.е. композицию $ \pi$ и $ \varphi$, определенную как $ (\pi\circ\varphi)(v)=\pi(\varphi(v))$) проверяющему. (Примечание. Доказывающий рассматривает любой $ \sigma\neq 2$ как $ \sigma=1$.)

4) Второй шаг проверяющего. Если сообщение обозначаемое $ \psi$, полученное от доказывающего, является изоморфизмом между $ G_\sigma$ и $ G'$, то проверяющий выдает 1 (т.е. принимает доказательство), в противном случае 0.