# 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

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.