Determining isomorphism for multiple graphs

146 Views Asked by At

enter image description here

Question: Determine the pairs of isomorphic graphs.

My answer so far: The first three graphs have 8 vertices with 3 degree. The last one has 2 vertices with 4 degree so I automatically eliminated that one. Then I determined the cycle length for each of the 4 possible graphs and found that they all had the same cycle length.. so now, it has passed 4 of my tests: edges, vertices, degrees, cycle length, would this suffice in saying that all 4 are isomorphic to each other?

1

There are 1 best solutions below

12
On BEST ANSWER

The only foolproof way to show that two graphs are isomorphic is to show an actual isomorphism between them.

If you try that for your four graphs you will find that this is possible for some of the pairs -- but not for others.

Hint: At least one of the four first graphs contains an edge that is part of exactly one 4-cycle. At least one other graph does not have such an edge.

Alternative hint: The second graph is obviously bipartite. The fourth graph is not bipartite, because it contains a cycle of length 5.