Isomorphism, two graphs

Question

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?

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