4. Show that the following problems are in NP (a) Given two graphs G = (V,E) and H = (W, F), we say G, H are isomorphic if there exists a bijection ? : V W such that for any two u, v E V, {u,v} E E if and only if fo(u), ?(v)) (i.e., two vertices u, v E V are adjacent if and only if {o(u),o(v)) are adjacent Let GRAPHIsoMORPHISM (G, H): G.H are isomorphic graphs}. Show that GRAPH SOMORPHISM ?s in NP. (b) Given a graph ?-(V,E), a subset of vertices I is a dominating set if every vertex in the graph is either in 1 or adjacent to a vertex in 1. Let DOMINATINGSET = {(G, k) : G has a dominating set of size k). Show that DOMINATINGSET is in NP. 4. Show that the following problems are in NP (a) Given two graphs G = (V,E) and H = (W, F), we say G, H are isomorphic if there exists a bijection ? : V W such that for any two u, v E V, {u,v} E E if and only if fo(u), ?(v)) (i.e., two vertices u, v E V are adjacent if and only if {o(u),o(v)) are adjacent Let GRAPHIsoMORPHISM (G, H): G.H are isomorphic graphs}. Show that GRAPH SOMORPHISM ?s in NP. (b) Given a graph ?-(V,E), a subset of vertices I is a dominating set if every vertex in the graph is either in 1 or adjacent to a vertex in 1. Let DOMINATINGSET = {(G, k) : G has a dominating set of size k). Show that DOMINATINGSET is in NP