Answer to Question 4-5

It suffices to give a polynomial time verifier for GIP.

Evidence. A renumbering of the vertices of G and another renumbering of the vertices of H. (A renumbering is given as a table showing each old vertex number and the corresponding new vertex number.)

Check. The evidence is satisfactory if all of the following are true.

1. G and H have the same number of vertices.
2. In the renumbered graphs, each edge in G is also an edge in H.
3. In the renumbered graphs, each edge in H is also an edge in G.