Two graphs G1 = (V1, E1) and G2 = (V2, E2), such that V1 = V2 = {1, 2, , n} are isomorphic if there is a one-one, onto function : {1, 2, , n} {1, 2, , n} such that for every i, j {1, 2, , n}

E1 <(i), (j)> E2

Show that the following decision problem in in NP.

Problem: Isomorphism Input

Instance: Two graphs G1 = (V1, E1) and G2 = (V2, E2) where V1 = V2 = {1, 2, , n}

Decision: Are G1 and G2 isomorphic?