How to find isomorphism using matrices?

Question

I'm searching for an easy way to give an isomorphism between two graphs since I never see it with my pair eyes and I found the following answer: This one

I tried applying it in a situation where the vertices have the same degree and things got messy and it was harder to apply it when the vertices have different degrees. This is where I tried to apply it and I got an answer but I'm sure my answer is wrong since it's based on just comparing the two matrices and saying what I thought the answer was. So my answer is: $ k=8, a=2, b=1, e=7,\ h=6, g=4, d=3, f=9, i=10, c=5 $

Is there any way to do this better or can someone give an explanation how one can apply the matrix way to give the isomorphism in this case?

Answer 1

Your proposed mapping is not an isomorphism because it sends $b$ to $1$ and $c$ to $5$ and there is an edge between $b$ and $c$ but there isn't an edge between $1$ and $5$.

Usually, the best way to tell if two graphs are isomorphic is by finding structural properties of the graphs. Informally, a structural property is one that can be defined independently of the labels of the vertices. For example, if one graph contains a cycle of length $k$ and the other does not, the graphs cannot be isomorphic. If you can't find a structural property in one graph that is not present in the other, then you can try to discover an isomorphism by aligning the structural features of the two graphs.

Now let's focus on your graphs. Call the graph on the left $X$ and the one on the right $Y$. First, we observe that in both graphs, each vertex has degree exactly $3$ (i.e. the graphs are $3$-regular), but this doesn't help us distinguish the graphs.

Looking at $X$, we see that there are two cyclic subgraphs $A = \{a f, k, i, b\}$ and $B = \{d, h, c, e, g\}$ containing $5$ vertices each. Now, $A$ has the property that each vertex in $A$ is connected to exactly two other vertices in $A$ and exactly one in $B$. A similar statement holds for $B$.

Our goal is to find analogues of $A$ and $B$ in $H$. If none exist, then the graphs are not isomorphic. If they do exist, we will try to use them to find an isomorphism.

Looking at $H$ for a moment, we discover the cyclic subgraphs $A' = \{2, 3, 9, 10, 1\}$ and $B' = \{5, 7, 4, 6, 8\}$. If we assume that $A$ maps to $A'$, then suppose that our mapping $\phi$ sends $a$ to $2$. Then $\phi(d) = 5$. Continuing further, we obtain the mapping $\phi$ defined by \begin{align} a & \mapsto 2 \\ f & \mapsto 3 \\ k & \mapsto 9 \\ i & \mapsto 10 \\ b & \mapsto 1 \\ d & \mapsto 5 \\ h & \mapsto 7 \\ c & \mapsto 4 \\ e & \mapsto 6 \\ g & \mapsto 8 \end{align}

It's clear that $\phi$ is a bijection, so we can verify that $\phi$ is an isomorphism by checking that

1. when restricted to $A$, it is an isomorphism to $A'$,
2. when restricted to $B$, it is an isomorphism to $B'$ and
3. that it maps the edges between $A$ and $B$ to the edges between $A'$ and $B'$.

It is slightly tedious but not difficult to verify that all three of these properties hold. If desired, this could be done by computing the adjacency matrix of the image of $X$ under $\phi$ and noting and it is equal to the adjacency matrix of $Y$.

Answer 2

I may be wrong but from the matrix example you found, I can say that using matrices is not for finding the isomorphism directly but checking (we can say proving as well) whether the isomorphism we found is correct or not. Because in your example, notice that s/he already knows the isomorphism between graphs as "(A B C D E F G) = (7 4 3 6 5 2 1)".

In the case of Petersen graph (the graph on the left), actually you can find an isomorphism if you can be more systematic. First of all, let us say $G$ is the Petersen graph (on the left) and $H$ is the graph on the right.

There is a graph isomorphism $\theta: G \rightarrow H$ if and only if for any adjacent vertices $x,y \in V(G)$, $\theta(x)$ and $\theta(y)$ is adjacent in $H$ and for any non-adjacent vertices $u,t \in V(G)$, $\theta(u)$ and $\theta(t)$ are non-adjacent in $H$.

I am writing the definitions because your answer is not correct and you can observe it by using the definition. For example, you map $b \rightarrow 1$ and $g \rightarrow 4$. In $H$, notice that vertices $1$ and $4$ are adjacent but in $G$, vertices $b$ and $g$ are not adjacent. So your mapping does not give an isomorphism. Instead of trying it randomly, you can use the symmetry of the graphs.

Let's start with the vertex $a$ and let's say $\theta(a) = 2$, that is $a \rightarrow 2$ (After this example, I will always use $\theta$ representation). Then notice that vertices $b$, $d$ and $f$ are adjacent to $a$. Let's say $\theta(b) = 1$, $\theta(f) = 3$ and $\theta(d) = 5$. From here, I suggest you to choose your next vertex from one of the vertices that you have mapped already. So let's choose the vertex $d$ and find its adjacent vertices. Those are $a$, $g$ and $h$. We have already mapped $a$, so for $g$ and $h$, we have only two options (Because in $H$, $5$ is adjacent to $2$, $7$ and $8$ and we have mapped $2$ already). So let's say $\theta(g) = 7$ and $\theta(h) = 8$.

Now for the rest, remember that we have $b \rightarrow 1$ and $h \rightarrow 8$. Notice that there is only one vertex adjacent to both $b$ and $h$ in $G$ (or $1$ and $8$ in $H$) and that is $c$ in $G$ (or $10$ in $H$). So we can map $\theta(c) = 10$. After this part, by a similar method, you can find other mappings as the following (with previous ones): $$\theta(a) = 2,\ \theta(b) = 1,\ \theta(c) = 10,\ \theta(d) = 5,\ \theta(e) = 9,\ \theta(f) = 3,\ \theta(g) = 7,\ \theta(h) = 8,\ \theta(i) = 4,\ \theta(k) = 6$$

Now we can prove that $\theta$ is an isomorphism by using the matrices. I just constructed two tables as matrices and I will put them on because how the matrices are constructed has already been explained in the example you have found. In this case, first matrix will have indexing as $a,b,c,d,e,f,g,h,i,k$ and the second matrix will have indexing as we found in isomorphism, that is, $2,1,10,5,9,3,7,8,4,6$. According to these indexing, the matrices will be as the following and they are the same if you reconstruct them from the start:

Since they are the same, we can conclude that $\theta: G \rightarrow H$ is a graph isomorphism.