6

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 $ t

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?

  • 3
    In general, constructing an adjacency matrix to deduce isomorphism probably isn't a fruitful approach. However, studying the linear algebraic properties of said matrices may be more fruitful. A quick test is to compute the eigenvalues of the two matrices. If they are not the same, then the two graphs are non-isomorphic. The converse is not true, however. There has been significant work on using spectral properties to test for isomorphism. Dan Spielman gives a brief overview here- http://www.cs.yale.edu/homes/spielman/561/2009/lect22-09.pdf – ml0105 Dec 23 '17 at 03:02

2 Answers2

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:

enter image description here enter image description here

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

ArsenBerk
  • 13,211
  • 1
    Whoever downvotes please explain a reason so that I could improve the answer... Today, I realized that my definition for graph isomorphism here wasn't right so I also edited my definition. Please even if you want to downvote, after downvoting, explain the reason. – ArsenBerk Jan 18 '18 at 17:39
  • Agreed. Looks like mine got unupvoted and downvoted too. – Qudit Jan 18 '18 at 21:05
  • Ah, yes your answer was downvoted too although it was a good one (using cycles is far shorter than my solution and a logical one). My definition was wrong so I can understand it but in your solution, I don't see any flaws right now. I think whoever did that do it randomly or something like that.. – ArsenBerk Jan 18 '18 at 21:08
  • 1
    FWIW, your definition could be worded a little better IMO, though I think that it falls far short of deserving a downvote. The phrasing "There is a graph isomorphism [...]" is slightly misleading. I would change it to say something like "The graphs G and H are isomorphic iff there exists a mapping $\theta$ such that ..." Also, thanks. Your answer is probably more understandable than mine for readers less familiar with graph isomorphism. – Qudit Jan 18 '18 at 21:11
  • Hmm, you may be right, I will handle that now. – ArsenBerk Jan 18 '18 at 21:14
  • 1
    Probably it's best just to ignore downvotes these days and try not to get too discouraged by them. When I started answers were only downvoted when they had serious problems or were clearly incorrect and otherwise people would just leave a comment (a much better practice IMO). However, recently people have become much more downvote happy on answers. – Qudit Jan 18 '18 at 21:16
  • 1
    You are right, this becomes discouraging when an answer well thought or long time spent gets downvotes without a reason but still it might have helped the OP, which should be our primary purpose while answering. – ArsenBerk Jan 18 '18 at 21:22
  • BTW, you can also avoid considering adjacent and non-adjacent vertices separately by saying that x, y are adjacent if and only if $\theta(x), \theta(y)$ are adjacent. – Qudit Jan 18 '18 at 21:23
2

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

Qudit
  • 3,221