Interactive proof system for graph nonisomorphism
The slide describes a proof system for graph non-isomorphism. This is a way for the prover to convince the verifier that the two graphs are non-isormorphic. The soundness of this proof system derives from the fact that it cannot work if the graphs are isomorphic. If $G_0 \equiv G_1$ then no matter what the prover does, the acceptance probability is only $1/2$.

How should we assign the bit? Proof systems don't work in this way. A proof system has two guarantees:


Completeness: if the input belongs to the language (in this case, the two graphs are not isomorphic), then there is a proof that convinces the verifier.
Soundness: if the input doesn't belong to the language (in this case, the two graphs are isomorphic), then no proof convinces the verifier.


When proving these two properties of the proof system, we specify a proof only in the first case. In the second case we have to show, instead, that no proof works. It's a different quantifier:


Completeness: if $G_0 \not\equiv G_1$ then there exists a proof which convinces the verifier with probability 1. (When proving completeness, we need to specify the proof that convinces the verifier.)
Soundness: if $G_0 \equiv G_1$ then all proofs convince the verifier with probability 1/2. (When proving soundness, we don't need to specify a proof. Indeed, we need to show that all proofs perform badly. In a sense, a proof is given to us, and we have to show that it doesn't convince the verifier.)