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

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?

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

  • $\begingroup$ Wouldn't that last bit about the first being bipartite and not the second be enough? $\endgroup$ – Semiclassical Sep 25 '14 at 17:39
  • $\begingroup$ Yes I guess it would $\endgroup$ – HBeel Sep 25 '14 at 17:41

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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.