Answer to Question 4-6

Here is a polynomial time verifier for SIP.

Evidence.

1. A subgraph S of G, indicated by a set of vertices and a set of edges, using the original vertex numbers in G.
2. A numbering of the vertices of S.
3. A numbering of the vertices of H.

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

1. S is a subgraph of G. Just check that the vertices in S are a subset of the vertices in G and the edges in S are a subset of the edges in G and no edge in S is incident onf a vertex that is not in S.
2. S and H have the same number of vertices.
3. Using the new vertex numberings given in parts (b) and (c) of the evidence, check that every edge in S is also an edge in H and every edge in H is also an edge in S.