[darek9576]

I have to prove that graph homomorphism between any undirected graph G and complete graph K3 is in NP.

However, this problem is exactly the same as 3 - colourability problem. So my question is: if i show that 3-colourability is in NP, do i show my original case?

Thanks for answers.

[mostyfriedman]

well if you prove that the 2 problems are equivalent and that one of them is in NP, then you're good. But you have to prove they are equivalent first.

[Nikitin]

How are these two problems equivalent?

Also, that homomorphism problem is solvable in constant time, so of course it's in NP as well.

Nevermind, I have mistaken "homomorphism" for "isomorphism". It's not constant of course. Easy to prove it's NP using verifiers. Still don't see how it's equivalent to 3-colorability though.

This post has been edited by Nikitin: 23 February 2012 - 07:13 PM

[macosxnerd101]

I'm going to move this to Computer Science. I know I've moved similar topics of yours to CS before. Please post in the appropriate section. Thanks!