# 3-Coloring Graph problem

Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is NP instead of NP-complete?

$$\mathrm{3COLOR} = \{\langle G \rangle \mid G \text{ is colorable with 3 colors}\}$$

• It sounds like you want to prove 3COLOR belongs to NP after you have proved it is NP-complete. Is that your intention? – Apass.Jack May 5 at 19:13
• This seems like a homework question. What have you tried so far? Have your proved 3-Coloring is NP-complete already? To prove it is NP you need a polytime verifier for a certificate of 3-Coloring. Can you think of one? – ryan May 5 at 21:31
• Yes, i have already proved it as np complete. – snape May 6 at 5:09
• Yes Apass.Jack that's exactly my intention. – snape May 6 at 5:12

Since 3-Colors is NP-Complete, it is also in NP.

Reminder:

$$\bullet$$ To prove a problem $$P$$ is in NP, we have to show a polynomial time "yes" certificate

$$\bullet$$ To prove a problem $$P$$ is NP-Complete, we have to show: $$P \in$$ NP and there is another problem $$X$$ which is NP-Complete, and $$X$$ can be reduced to $$P$$.

It is clear then, that:

$$P$$ is NP-Complete $$\Rightarrow P\in$$ NP.

The first condition is trivial, and the reduction to 3-SAT is widely known and can be found easily.