Question

Homework Problems Problem 12.8. Determine which among the four graphs pictured in Figure 12.24 are isomorphic. For each pair of isomorphic graphs, describe an isomorphism between them. For each pair of graphs that are not isomorphic, give a property that is preserved under isomorphism such that one graph has the property, but the other does not. For at least one of the properties you choose, prove that it is indeed preserved under isomorphism (you only need prove one of them)

Answer 1

Two graphs are isomorphic if (a) They have the same number of edges (b) They have same number of vertices (c) They have equal number of vertices with a given degree. Number of vertices in G_1 = 10 Number of vertices in G_2 = 10 Number of vertices in G_3 = 10 Number of vertices in G_4 = 10. Number of edges in G_1 = 15 Number of edges in G_2 = 15 Number of edges in G_3 = 16 Number of edges in G_4 = 15 Number of vertices in each graph = 10. Degrees of corresponding vertices = 3(a_11) Number of edges in Graph G_1,G_2, G_4 = 15 Number of loops in G_1 and G_2 = 6 therefore Graphs G_1 and G_2 are isomorphic.