Are these graphs isomorphic?

Question

Are these 2 graphs isomorphic? (sorry for the bad picture quality)

For the solution:

• 1) They both have 8 vertices
• 2) They both have 12 edges
• 3) They both have 8 vertices of degree 3
• 4) Is this enough to prove isomorphism?

Answer 1

No it is not enough. You can find a cycle of odd length in the second graph and you can't in the first. Convince yourself of this by explicitly showing a odd cycle and then vertex colouring the first with 2 colours to prove it's bipartite and hence doesn't contain odd cycles

Answer 2

Two graphs are said to be isomorphic if one is the redrawing of another.

That is, G1 isomorphic to G2 if and only if by drawing vertices of G1 in different position and joining the edges of G1 we can get the same diagram of G2.(forget the vertex and edge labelling)

Hence isomorphic graphs must have the same properties.

In your problem, the first graph is a bipartite graph.

The second graph has a cycle of length 5. Hence it is not a bipartite graph

The given graphs are not same graphs (not isomorphic)