1

My Question: If two graphs have the same vertice, same degree in each vertice, and the same amount of edges, would an adjacency matrix suffice in showing that they are or are not isomorphic?

What I have done: I have tried to regraph one of the graphs to try to match up with the other but with that being said I found out that they are not isomorphic. Now, to best explain to my professor (not just guessing), can I do an adjacency list that will 100% prove that my answer is correct?

enter image description here

Robert Miller
  • 317

1 Answers1

1

Let $G$ be the graph on the left and $H$ be the graph on the right. Then,

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

Here, $\theta$ is the bijection I was talking about but the name shouldn't confuse you, it is just one-to-one and onto function that takes a vertex in $G$ and outputs a vertex in $H$.

Now, in your example I think you are right about graphs being not isomorphic. Because notice that in $G$, there is a choice of two non-adjacent vertices with only one mutual adjacent vertex (such as $b$ and $h$ having a mutual adjacent vertex $a$), however in $H$, we can't choose two non-adjacent vertices with just one mutual adjacent vertex but we can choose them such that there is no mutual (such as $1$ and $7$) or two mutual adjacent vertices (such as $1$ and $3$ having mutual adjacent vertices $2$ and $4$).

If there were an isomorphism, we could have constructed a bijection using the definition and then, we would have been able to use adjacency matrices to prove our isomorphism. Otherwise, you cannot use adjacency matrices to prove whether there exists an isomorphism or not.

ArsenBerk
  • 13,211
  • I'm not really sure how to use bijection... I will draw out the graphs and show you. – Robert Miller Jan 17 '18 at 23:42
  • Yes, that would be better. By the way, you can also see this question: https://math.stackexchange.com/questions/2576547/how-to-find-isomorphism-using-matrices/2577112#2577112. I also answered this one and it was a nice example. How to construct bijection between vertices of two graphs is also shown there. – ArsenBerk Jan 17 '18 at 23:45
  • Edited my post. – Robert Miller Jan 17 '18 at 23:46
  • I edited my post, hope it helps. – ArsenBerk Jan 18 '18 at 00:19
  • Your definition of isomorphism makes every graph isomorphic to a complete graph. – Mariano Suárez-Álvarez Jan 18 '18 at 00:27
  • Still not sure how to prove that they are not isomorphic. We haven't gone over cycles in class so I can't really use that. – Robert Miller Jan 18 '18 at 00:29
  • @MarianoSuárez-Álvarez Well, I think you are right, I just made that definition by assuming $G$ and $H$ have the same number of vertices and edges (since otherwise, the result would be obvious). But now I checked wikipedia and the definition there is too similar to the definition I made. – ArsenBerk Jan 18 '18 at 00:34
  • @RobertMiller I didn't use cycle property. I just wanted you to notice the number of mutual adjacent vertices. If you didn't understand it, I can go over it by defining mutual adjacent vertex properly. – ArsenBerk Jan 18 '18 at 00:36
  • What do you mean by mutual adjacent vertices? – Robert Miller Jan 18 '18 at 00:38
  • For two non-adjacent vertices $x$ and $y$ and a vertex $z$, if there is an edge $xz$ and $yz$, $z$ is a mutual adjacent vertex of $x$ and $y$ (because it is adjacent to both $x$ and $y$). – ArsenBerk Jan 18 '18 at 00:41
  • @MarianoSuárez-Álvarez I corrected the definition, hope the flaw is disappeared. – ArsenBerk Jan 18 '18 at 00:45
  • @ArsenBerk Now, in your example I think you are right about graphs being not isomorphic. Because notice that in GG, there is a choice of two non-adjacent vertices with only one mutual adjacent vertex (such as bb and hh having a mutual adjacent vertex aa), however in HH, we can't choose two non-adjacent vertices with just one mutual adjacent vertex but we can choose them such that there is no mutual (such as 11 and 77) or two mutual adjacent vertices (such as 11 and 33 having mutual adjacent vertices 22 and 44). – Robert Miller Jan 18 '18 at 00:52
  • Based on this, since G has two non adjacent vertices with only one mutual and graph H does not, then this proves that they are not isomorphic? – Robert Miller Jan 18 '18 at 00:53
  • Yes, that's exactly what I was trying to say. If there is such a difference between two graphs, then we can say that they are not isomorphic (If there is such a difference, how can we convert one another or draw them as same as each other). – ArsenBerk Jan 18 '18 at 00:55
  • THANK YOU! There are so many ways but every person on here just explains without showing work it hurts... – Robert Miller Jan 18 '18 at 00:57
  • @RobertMiller You're welcome, people here may want you to learn yourself after their explanation so don't think they are lazy people not to show their work. In the beginning, I thought the graphs are isomorphic, then I noticed this and wanted to share. – ArsenBerk Jan 18 '18 at 01:02