# What is a graph isomorphism?

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the same, and get graph B. But I found a question and answer from the internet here:

http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf

Question 1.1.34

here is a screen shot below, and the three sub graphs shouldn't be isomorphic. For example, the first graph has 2 nodes of degree 3 and the other 2 don't.

Can someone explain this?

Thanks

• It should be mentioned, that two graphs are isomorphic if and only if there exists a way you can move vertices from the first graph around (dragging edges with them) and relabel them to make it look exactly like the second graph, but finding such a way to drag things around is usually quite difficult. It is much easier to show that they aren't isomorphic using invariant qualities about the graph (such as number of vertices of particular degree like you mention). It is unknown if the general problem is P, or NP complete. en.wikipedia.org/wiki/Graph_isomorphism_problem Jan 26, 2015 at 13:28