# Determining if two graphs are isomorphic

The answers are already given after the $=$ sign of each question. But I don't know how they arrived at these answers. What does it mean to say $f(A)=1$ and so on? I can't find the connection.

-
Make a list of which node is connected to which in both graphs, and look for correspondences. –  Ｊ. Ｍ. Nov 14 '10 at 23:39
@Arturo hmm are we sure that 'are' is the correct grammar for the question? If we're referring to a pair, then a pair is singular, in which case we use 'is isomorphic'. I had are before but I changed it because I'm not sure are is the correct word to use.. –  maq Nov 14 '10 at 23:52
@fprime: if "isomorphic" refers to "pair", then what is that pair isomorphic to? –  Arturo Magidin Nov 15 '10 at 0:09
Wait what? I was just talking about the title of the question –  maq Nov 15 '10 at 0:11
@Rahul Narain: Heh; images of hurricanes inside teacups are coming to mind... –  Arturo Magidin Nov 15 '10 at 0:39

A graph can be thought of as a pair $(V,E)$, where $V$ are the vertices and $E$ are the edges. An isomorphism between two graphs, $G_1 = (V_1,E_1)$ and $G_2=(V_2,E_2)$ means a function $f\colon V_1\to V_2$ that is bijective between the vertices (one-to-one and onto, so every vertex in $G_1$ is mapped to a vertex of $G_2$, and each vertex in $G_2$ is the image of one and only one vertex in $G_1$) and for vertices $v_1,v_2$ of $G_1$, $v_1$ is adjacent to $v_2$ in $G_1$ if and only if $f(v_1)$ is isomorphic to $f(v_2)$ in $G_2$.

So, the answer they give is a description of an isomorphism between the second graph and the first: it is a function from the set of vertices of the second graph, $\{A,B,C,D,G,H,I,J\}$, and the vertices of the first graph, $\{1,2,3,4,5,6,7,8\}$, with the property that two vertices in the second graph $x$ and $y$, are adjacent if and only if $f(x)$ is adjacent to $f(y)$ in the second graph. For instance, $A$ and $I$ are adjacent, so $f(A)=1$ needs to be adjacent to $f(I)=4$ (which it is), and $A$ and $J$ are not adjacent, so $f(A)=1$ should not be adjacent to $f(J)=7$ (which it is not). You can check that the function described actually is an isomorphism by checking that every pair of adjacent vertices are sent to adjacent vertices, and every pair of non-adjacent vertices are sent to non-adjacent vertices.

Now... how did they come up with $f$ in the first place? Well, let's think about the graphs.

In the second graph, each vertex is adjacent to exactly three vertices, so if there is going to be an isomorphism between the two graphs, then every vertex in the first graph needs to be adjacent to exactly three vertices. This is indeed true, which is a good start for a possible isomorphism (if it wasn't true, we would have no hope of having an isomorphism, and if fact we would know that no isomorphism exists).

Also, the second graph is "bipartite": you can divide the vertices into two groups in such a way that all edges are between the two groups, with no edges between vertices in the same group. If we are going to find an isomorphism between this graph and the first, we need to be able to also separate the vertices of the first graph into two groups of four, so that all edges are between the groups and no edge goes from one vertex in a group to another vertex in the same group.

Can we divide the vertices in the first graph into two sets of four so that all edges are between the sets? Well, let's see: if $1$ is in one set, then $2$, $4$, and $5$ should be on the other set because there can be no edges between two vertices in the same set (remember: we are trying to check if there is an isomorphism). Notice that if we do this, then there better not be any edges between $2$, $4$, and $5$, because we are going to put them in the same set (the set which is not the set with $1$ in it). Good, no edges between any of $2$, $4$, and $5$. And $6$ and $3$ need to be with $1$, because they are both adjacent to $2$, and so they cannot be in the same set with $2$; the only possibility left is the set with $1$ in it. That means that $1$, $3$, and $6$ need to be in the same set of vertices, which means there should be no edges between them (no edges between any two vertices in the same set, remember?). Good, no edges between any of $1$, $3$, and $6$. And $8$ needs to be with $1$, because it is adjacent to $4$. And so $7$ needs to be in with $2$, $4$, and $5$.

So, if we can find an isomorphism between the two graphs, then we can divide the vertices of the first graph into two sets, just like the ones in the second graph, and one set needs to have $1$, $3$, $6$, and $8$, and the other set needs to have $2$, $4$, $5$, and $7$. And all edges should be between the sets, not no edges between vertices in the same set. This all holds, so we are on the right track!

So, can we define an isomorphism based on this? There is a lot of symmetry, so it probably does not matter where we send $A$, just so long as we do things right. So let's send $A$ to $1$: $f(A)=1$. Because $G$, $H$, and $I$ are adjacent to $S$, we need $f(G)$, $f(H)$, and $f(I)$ to be adjacent to $f(A)=1$; so $f(G)$, $f(H)$, and $f(I)$ need to be $2$, $4$, and $5$ in some order. Say $f(G)=2$. Then $f(H)$ needs to be either $4$ or $5$. If we make it $5$, then since $2=f(G)$ and $5=f(H)$ have only two mutually adjacent vertex (namely $1$ and $6$), and $G$ and $H$ have only two mutually adjacent vertices (namely $A$ and $B$), and $A$ already maps to $1$, then we need $B$ to map to $6$. So so far we have $f(A)=1$, $f(B)=6$, $f(G)=2$, and $f(H)=5$. $B$ is adjacent to $J$, which is not adjacent to $A$, so $f(J)$ needs to be adjacent to $f(B)=6$, but not to $f(A)=1$; and it needs to be in the same group as $2$ (so it has to be one of $2$, $4$, $5$, or $7$); $5$ and $2$ are already taken, $4$ is adjacent to $1$, so we need to make $f(J)=7$.

So so far we have $f(A)=1$, $f(B)=6$, $f(G)=2$, $f(H)=5$, and $f(J)=7$. What about $C$? $f(C)$ needs to be adjacent to $f(G)=2$ and to $f(J)=7$, but not to $f(H)=5$; the only possibility not yet taken is $f(C)=3$. Continuing this way you get the isomorphism they give.

Note: this is not the only possible isomorphism; other choices lead to other isomorphisms, of which there are many because the graphs are so symmetric.

-
Ok sorry I did not understand anything you did in the second paragraph :/ –  maq Nov 14 '10 at 23:47
@fprime: I'll rewrite. –  Arturo Magidin Nov 15 '10 at 0:09
Woah. Thanks a lot man you went above and beyond. This really helped! –  maq Nov 15 '10 at 0:42