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