9 Determine whether any two of the simple graphs G1 G2 and G

9. Determine whether any two of the simple graphs G1, G2, and G3 are isomorphic. If they are, give a vertex function that defines the isomorphism. If they are not, give an isomorphic invariant that they do not share.

Solution

Two graphs that contain the same number of vertices and edges are connected in the same way

In the first graph, there are 6 vertices and 6 edges

In the second graph, there are 6 vertices and 7 edges

In the third graph, there are 6 vertices and 6 edges

Since the first graph has 6 edges and second graph has 7 edges, hence the graphs are not isomorphic

The first and third graph can be isomorphic since they are having equal edges and equal vertices.

The first and third graph can be isomorphic since there exists one vertex in the third graph has degree (3) i.e. vertex w2 is connected with w1,w3 and w4 and one vertex u3 is also of degree 3

u3 is similar to w2, u1 is similar to w3 and u6 is similar to w4, u4 is similar to w1 and u5 is similar to w6 and u2 is similar to w5

Hence the first and third graph are isomorphic with each other