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?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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
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)