Общий вход: пара графов
и
. Пусть - изоморфизм между и , т.е. биективное отображение множества вершин на множество вершин такое, что
тогда и только тогда, когда
.
1) Первый шаг доказывающего. Доказывающий выбирает случайную изоморфную копию графа и отправляет её проверяющему . Т.е доказывающий выбирает наугад перестановку из множества перестановок множества вершин и строит граф с множеством вершин и множеством ребер
Примечание. Если входные графы изоморфны, как утверждает доказывающий, то граф, отправленный на первом шаге изоморфен обоим входным графам. А если входные графы не изоморфны, то никакой граф не может быть изоморфным обоим входным графам.
2) Первый шаг проверяющего. После получения графа
от доказывающего, проверяющий просит доказывающего показать изоморфизм между и одним из входных графов, выбранным наугад проверяющим. А именно, проверяющий равномерно выбирает
и отправляет его доказывающему (который должен показать изоморфизм между и ).
3) Второй шаг доказывающего. Если сообщение, полученное от проверяющего, равно 2, то доказывающий отправляет проверяющему. В противном случае (т.е. если
) доказывающий отправляет
(т.е. композицию и , определенную как
) проверяющему. (Примечание. Доказывающий рассматривает любой
как .)
4) Второй шаг проверяющего. Если сообщение обозначаемое , полученное от доказывающего, является изоморфизмом между и , то проверяющий выдает 1 (т.е. принимает доказательство), в противном случае 0.