# Showing that 3-colorable is NP-complete

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color?

I'm aware we can show that 3-colorable is an NP-complete problem by reducing 3-SAT to it. But I'm wondering is it possible to reduce clique to it?

I know for example that if a graph with n vertices contains a subgraph which is a clique of size k, then you need at least k colors (that is, the chromatic number is at least k).

So could we say that if a graph contains a clique of size 4, then it is not 3-colorable, and vice versa?

Edit: Hmm..upon further thought, maybe the reduction wouldn't work because in order to reduce clique, you can't fix ahead of time that you're looking for a clique of size 4? The size of the clique would be arbitrary..

• What have you tried? Have you tried looking for a proof of your claim? Have you tried looking for a counterexample? Try some small graphs. – D.W. Mar 9 '16 at 16:26

A problem $P$ being NP-hard means that all problems in NP can be reduced to $P$. That's by definition. Working out the exact reduction needed can be tricky, which is why one usually looks for a somehow similar problem to prove hardness. You probably wouldn't try to directly reduce MINIMUM INTERVAL GRAPH COMPLETION to Tetris to prove its hardness.