Are these two graphs isomorphic?
Isomorphism between two particular graphs
-
0http://en.wikipedia.org/wiki/Graph_isomorphism β 2012-12-07
3 Answers
The two graphs can be redrawn to like the ones below; which is which?
Can you explain why these two graphs are not isomorphic? HINT: Does the first graph contain a $5$-cycle?
-
0@user1551: If itβs what you happen to see first. (It probably does make an easier hint, but in fact it was the $5$-cycle that leaped out at me.) β 2012-12-07
When dealing with isomorphism questions, I always start by trying to prove they are not isomorphic. To do this, I need to demonstrate some structural invariant possessed by one graph but not the other. A structural invariant is some property of the graph that doesn't depend on how you label it. Examples are the degree sequence of the graph, the number of cycles of different sizes, its connectedness, and many others.
Brian Scott's redrawing of your two graphs helps immensely to see that one graph possesses a $5$-cycle and one does not. No matter how you label the two graphs, one will have a $5$-cycle and one will not, so they cannot possibly be isomorphic.
For this specific case, yes they are. checking the isomorphism of graphs is NP-complete though.
EDIT: no they aren't ! degree n=3 vertices are at the opposite corners of the square at one-- not at consecutive corners.
-
0Determining whether or not the [graph isomorphism problem](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) is NP-complete is a longstanding problem in theoretical computer science. (Are you getting this confused with the [subgraph isomorphism problem](http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem)?) β 2013-05-14