Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Are these two graphs isomorphic?

enter image description here

share|improve this question
2  
Isomorphic just means that the mathematical structure is the same, only the names/labels of the elements change. So if you can find a substitution for each $A_i$ and $C_i$ where i=1,2,3,4,5,6, and after that it's the same graph, you know that it's isomorphic –  MSKfdaswplwq Dec 7 '12 at 22:50
    
add comment

3 Answers 3

The two graphs can be redrawn to like the ones below; which is which?

enter image description here

Can you explain why these two graphs are not isomorphic? HINT: Does the first graph contain a $5$-cycle?

share|improve this answer
1  
Checking the adjacency of the two degree-3 vertices is a bit easier than checking the existence of a 5-cycle :-D –  user1551 Dec 7 '12 at 23:36
    
@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.) –  Brian M. Scott Dec 7 '12 at 23:38
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Determining whether or not the graph isomorphism problem is NP-complete is a longstanding problem in theoretical computer science. (Are you getting this confused with the subgraph isomorphism problem?) –  Douglas S. Stones May 14 '13 at 1:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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