Problem 2. Consider the following two graphs:G₁V₁=(a,b,c,d,e,f,g)E₁={{a,b),(a,d},{b,c}),(b,d},{b,e},{b,f},{c,g},{d,e},{e,f},{f,g}}.G₂V2=(V1, V2, V3, V4, VS, V6, V7),E2={{V1,V4},{V1,VS),{V1,V7), (v2,v3), (V2,V6},{V3,VS), (Va,V7},{V4,VS),(VS,VG),(VS,V7}}Let f: V₁ V₂ be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is givenby the following table:Xdff(x)V4V6V₂V3a. Does f define an isomorphism between Graph 1 and Graph 2? Justify your answer.b. Define a new function g (with gef) that defines an isomorphism between Graph 1 and Graph 2.c. Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.aabVsdсV₁bGV7

By the function f we convert all the edges of graph 1 in the new form of vi So, new edges are (v4,v5), (v4,v6) , (v5,v1), (v5,v6), (v5,v2), (v5,v3), (v1,v7), (v6,v2), (v2,v3), (v3,v7) Now comparing, if we get same set of edges. The edges are not same. For example this does not contain (v1,v4) Defining a new function, We observe degree of edges, and then find the required function deg(a)=2 deg(b)=5 deg(c)=2 deg(d)=3 deg(e)=3 deg(f)=3 deg(g)=2 And deg(v1)=3 deg(v2)=2 deg(v3)=3 deg(v4)=2 deg(v5)=5 deg(v6)=2 deg(v7)=3 This implies b is mapped to v5 a has three options v2,v4,v6. But a is connected to b, so a now has v4, v6 only. Let a be mapped to v4. Then v4 is connected to v5 and v1. v1 has degree 3. a is connected to b and d. Therefore d must be mapped to v1. Now d is connected to a, b and e v1 is connected to v4,v5,v7. Therefore, till now our assumptions work. Now e must be mapped to v7. e is connected to b, d and f v7 is connected to v1, v3, v5 This implies f must be mapped to v3 Now, f is connected to b, e and g. And v3 is connected to v2, v5, v7. This implies g must be mapped to v2 v2 is connected to v3, v6 g is connected to c and f. Implies c must be mapped to v6. This forms an isomorphism. There is no element in graph with degree 5 Hence this graph is not isomorphic to any of the above graphs.