# Given two non-isomorphic graphs with the same number of edges, vertices and degree, what is the most efficient way of proving they are not isomorphic?

After being given the following two graphs with the same number of edges, vertices and degree, I'm trying to show that they are not isomorphic. At least they seem to be non-isomorphic from the time I spent playing with them on graphcreator. Is there an efficient way of solving this problem, or is this likely one of those problems I'm just not expected to solve conclusively?

-

## migrated from mathematica.stackexchange.comMar 6 '14 at 21:15

This question came from our site for users of Mathematica.

In general, it is not known whether graph isomorphism can be checked efficiently. In this case, however, the first graph is $K_8$ with two disjoint squares $ACHF$ and $BDGE$ removed; the second graph is $K_8$ with an 8-cycle $AFEBHCDG$ removed. So the two are not isomorphic. – Rahul Mar 6 '14 at 19:57
"BLISS" and "NAUTY" are some well known programs/algorithms for checking isomorphism. They are far from simple though. – Szabolcs Mar 6 '14 at 20:15

## 2 Answers

In this case, you can check whether the complementary graphs are isomorphic. The complement to the first graph is two disjoint $4$-cycles. The complement to the second graph is an $8$-cycle. Since these graphs are clearly not isomorphic, the original graphs aren't either.

-
This is a useful simplification whenever the degree is large (bigger than half the number of vertices). However, it won't usually be quite this effective. In this case , connectivity of the complement was enough to establish non-isomorphism, but it is useful to have a wide array of invariants to calculate. This is useless when graphs are isomorphic, and not always useful when they aren't, but it works in practice. – Aaron Mar 6 '14 at 22:21
Yes, the more graph invariants you can find (that can be computed or at least compared in polynomial time), the better. That being said, it isn't known whether GRAPH-ISOMORPHISM is in P, so whatever list of graph invariants you give isn't going to work for all pairs of non-isomorphic graphs. – mjqxxxx Mar 7 '14 at 16:26
Yes, that is what I meant by my final sentence. The "this" was referring to computing graph invariants. Out of curiosity, do you know the time complexity to compute the characteristic polynomial of the adjacency matrix, or how good an invariant it is? Expansion by minors has horrible run time generically, but there may be better algorithms and it might not be so bad for sparse matrices. – Aaron Mar 7 '14 at 16:47
I think it can be found in polynomial time. Even very small non-isomorphic graphs may have the same characteristic polynomial: see the 5-node example at mathworld.wolfram.com/CharacteristicPolynomial.html. – mjqxxxx Mar 7 '14 at 22:07

When the eigenvalues of the adjacency matrices are different the graphs are not isomorphic.

-