# Isomorphism between two particular graphs

Are these two graphs isomorphic?

-
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 – Applied mathematician Dec 7 '12 at 22:50

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?

-
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

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.

-
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