Hi I'm taking the course 6042 of MIT of discrete math (mathematic for computer science) and now I am encountering this problem:
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).
When I read the explanation and the answer I got the Graph $G_1$ is $G_3$ is isomorphic is Ok to me (because they preserve the degree of each individual node in the graph), but when the answer show the isomorphic function f to transform $G_1$ and $G_3$, it baffles me (I get the intuition of the isomorphism and clear about it, but cannot know why the function make sense)
G1 and G3 are isomorphic. In particular, the function $f : V_1 → V_3$ is an isomomorphism, where
$f(1) = 1 $
$f(2) = 2 $
$f(3) = 3 $
$f(4) = 8 $
$f(5) = 9 $
$f(6) = 10 $
$f(7) = 4 $
$f(8) = 5 $
$f(9) = 6 $
$f(10) = 7$
from $f(4)$ i'm kinda clueless, because I don't know what type of what type of shifting you apply to these points, basically we just match those points because they connect to each other without any constrain (I know that if two nodes in the original graph ($G_1$) have no common edge, all the isomorphism of $G_1$, these two vertices must have no connection)
Can anyone explain this to me, and I wonder if there is exist other type of function matching all point of $G_1$ to $G_3$ that follow the rule of isomorphism.
Thanks in advance
Best Answer
The condition that you need to check, to verify that $f$ is an isomorphism, is that for all $i,j\in\{1,2,\ldots,10\}$ the pair $(i,j)$ is an edge if and only if the pair $(f(i),f(j))$ is an edge of the other graph.
Note that $G_1$ looks very symmetric. For example, rotating it you can make it coincide with itself. Those would be automorphism $g:G_1\to G_1$. Actually, for any way that you want to permute the vertices $1,2,\ldots,5$, there is a unique way to make the vertices $6,7,\ldots, 10$ to map to vertices $6$ to $10$ to get an automorphism. Every time you get one such $g$, then $f\circ g:G_1\to G_2$ gives you another isomorphism between $G_1$ and $G_2$.