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$
  • 2
    $\begingroup$ Have you looked up what it means for graphs to be isomorphic? $\endgroup$ – Morgan Rodgers Aug 7 '16 at 12:17
  • 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$ – Gerry Myerson Aug 7 '16 at 12:54
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$
  • $\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 Aug 7 '16 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$ – Luiz Cordeiro Aug 8 '16 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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