Graph Theory: Isomorphism

Question

I am trying to do MIT ocw course 6.042: Math for CS. Could anyone help with this one? I couldn't really understand the concept of isomorphism. What exactly do they mean by " preserved under isomorphism"?.

Determine which among the four graphs pictured in the Figures are isomorphic. If two of these graphs are isomorphic, describe an isomorphism between them. If they are not, give a property that is preserved under isomorphism such that one graph has the property, but the other does not. For at least one of the properties you choose, prove that it is indeed preserved under isomorphism (you only need prove one of them).

The graphs are given below in the link: It is from MIT 6.042 Problem set 4. Problem 3 Part(b): http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/assignments/MIT6_042JF10_assn04.pdf

Answer 1

$G_2$ has vertices with $4$ outer-edges (namely, 10 and 8), and the other graphs don't.

$G_4$ has $4$-cycles (e.g. 3-4-10-8), and $G_1$ and $G_3$ don't.

$G_1$ and $G_3$ are isomorphic. I'll let you try to figure out the isomorphism yourself. You can use this tool: https://illuminations.nctm.org/Activity.aspx?id=3550 to draw the graphs and move the vertices around, which should help you find an isomorphism.

Hint: one possible isomorphism, in the firection $G_1\to G_3$, maps $1\mapsto 1$, $2\mapsto 2$, $3\mapsto 3$, $4\mapsto 4$, $5\mapsto 10$).

Answer 2

https://en.m.wikipedia.org/wiki/Graph_isomorphism

The Wikipedia article gives the definitions but they may not be easy to understand. The basic intuition is that if you can move the vertices of a graph without changing the connections between vertices and edges so that the graphs look the same, then they are isomorphic. In other words, take any graph you know and move one of the vertices to the other side. All the connections and other properties will be the same but it will look different.