Graph nonisomorphism is in IP

Using adjacency-matrix graph encodings, the verifier first checks the two encoded inputs are graphs, rejecting malformed inputs. If their vertex counts differ, it accepts: such graphs cannot be isomorphic. Both checks are deterministic polynomial-time. In the remaining case relabel both vertex sets as $\{1,\dots ,n\}$ and use the bounded-rejection protocol The graph-nonisomorphism interactive protocol. Its factorial arithmetic and four bounded draws meet the verifier's worst-case polynomial time and random-bit budget. If $G_0\cong ̸G_1$, every permutation, including the fallback identity, leaves $H$ in exactly one of the two isomorphism classes, so an unbounded prover answers correctly with probability $1$.

If $G_0\cong G_1$, the successful-draw branch gives the same uniform distribution $U$ of $H$ for both values of $b$. The fallback has probability $\epsilon <1\mathrm{/}16$ and gives $H=G_b$, so the two challenge distributions are $(1-\epsilon )U+\epsilon {\delta }_{G_0}$ and $(1-\epsilon )U+\epsilon {\delta }_{G_1}$. Their total-variation distance is at most $\epsilon$. With a uniform hidden bit $b$, any prover's best guess from $H$ has success probability at most $(1+\epsilon )\mathrm{/}2<17\mathrm{/}32$; this follows directly by summing, for each possible $H$, the larger of its two joint probabilities.

Run two fresh independent challenges and accept only when both answers are correct. On a no instance, after every first transcript the second challenge still has fresh private coins, so even an adaptive prover has conditional success probability below $17\mathrm{/}32$. Thus two-copy soundness is below $(17\mathrm{/}32{)}^2=289\mathrm{/}1024<1\mathrm{/}3$, while completeness remains $1$. The two copies retain a fixed polynomial worst-case budget, so The class IP applies.