0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ If every graph isomorphic to a given graph with Property P has Property P, then we say Property P is preserved by isomorphism. For example, every graph isomorphic to a graph with 17 vertices has 17 vertices, so having 17 vertices is preserved under isomorphism. $\endgroup$ Commented Aug 7, 2016 at 12:54

2 Answers 2

0
$\begingroup$

$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$).

$\endgroup$
2
  • $\begingroup$ I tried to see the isomorphism between G1 and G3 but could not see it. I played with G1 and G3 in the animation link but these don't look isomorphic. I am comparing vertex 1 in G1 with vertex 1 in G3. Can it be that that e.g vertex 3( or any other no.) in G1 is related to vertex say 5 in G3? I If yes, then there are just too many possibilities to check. <br> And yeah thanks for the great link. $\endgroup$
    – muneeb
    Commented Aug 7, 2016 at 18:04
  • $\begingroup$ @Solomon You can draw $G_1$ in the tool and move vertices 1 to 5 around, as in the hint, so that they are in the same position as its image in $G_3$. Then you simply need to move the other ones around in order to obtain $G_3$, and this will give you the isomorphism. For example, in $G_3$, the vertices 1,3 and 6 are connected to 2. The hint already states that 1, 2 and 3 in $G_3$ are associated to 1, 2 and 3 in $G_1$, so 6 in $G_3$ will be associated with the only other vertex connected to 2 in $G_1$, namely 9. You can continue these arguments and find the remaining associations of vertices. $\endgroup$ Commented Aug 8, 2016 at 2:24
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .