0
$\begingroup$

I have a question regarding the general method of determining whether two graphs are isomorphic to one another.

I understand that for small graphs one may look at a graph and determine rather easily by inspection whether or not two graphs are isomorphic.

I also understand that a way to show that two graphs are not isomorphic is to show that one graph $G_1$ has an invariant property while another graph $G_2$ does not possess the same property. From what I understand, typically one shows that a graph is not isomorphic to another by utilizing invariant properties.

My question is whether showing two graphs possess invariant properties is enough to show that they are isomorphic. For example, if you show that two graphs possess two simple 3-cycles, does this automatically guarantee they are isomorphic?

Thanks!

$\endgroup$
  • $\begingroup$ In general, no. (Graph isomorphism is a strange problem, btw ... It's known to be in NP, but it's not known to be NP-complete!) $\endgroup$ – Christopher Carl Heckman Mar 8 '16 at 23:45
  • $\begingroup$ In fact, if you know who Laszlo Babai is, he showed that Graph Isomorphism is doable in quasipolynomial time, and it took him 35 years to prove that. You might want to read his paper. It is complicated, but if you work your way slowly, you may find a partial answer. $\endgroup$ – астон вілла олоф мэллбэрг Mar 9 '16 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.