I have a "Which of the following graphs are isomorphic?" question. The graphs are the same order and regular, which makes it quite difficult for me to prove why they are isomorphic, or find out why they are not. One thing I recognized is that, one of them is 2 colorable whereas the other one is not. Please prove that chromatic number is invariant under isomorphism, so that I can prove these two graphs are not isomorphic.

I am still struggling with the other two graphs, so my other question is: if the order and degree sequence are the same; what could be other invariant that will help me to prove they are not isomorphic (such as chromatic number helping me)? If everything seems to be the same, what is the formal proof? I suppose showing that the two graphs have equivalent adjacency matrices?

  • $\begingroup$ Hint: given a two-coloring of one graph, show that you can create a two-coloring of the other graph, supposing they are isomorphic. $\endgroup$ – Wojowu Jul 16 '18 at 15:41
  • $\begingroup$ @Wojowu I do not understand what you mean, and there are multiple questions, which one are you referring to? $\endgroup$ – Ninja Bug Jul 18 '18 at 13:58
  • $\begingroup$ I was refering to the question in the title, or more specifically, the fact that whether a graph is two-colorable should be preserved by isomorphisms (addressing the case of the two graphs you talk about in the first paragraph) $\endgroup$ – Wojowu Jul 18 '18 at 14:04
  • $\begingroup$ @Wojowu okay, but this does not seem like a formal proof. We just show that there is a supporting example by doing that. $\endgroup$ – Ninja Bug Jul 18 '18 at 14:08

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.