How to prove that the 4-coloring problem is NP-complete

$\begingroup$

I know that the 4-coloring problem is NP-complete, but I'm looking for a proof of that statement. Unfortunately, I haven't found a (for me) reasonable and clear proof.

I tried to reduce the 4-coloring problem to the 3-coloring problem and since that is NP-complete, the 4-coloring problem would be NP-complete. Still, I haven't found a solution for that. Does anyone have a solution?

$\endgroup$ 1

1 Answer

$\begingroup$

For every fellow person who is struggeling with the same proof, I came up with this solution: I created a 3 color tree. Then I added a vertex like Michal-Adamaszek proposed (thanks for the hint). Next I draw an edge from each of my 3 colored Graphs vertices to the new vertex. Since every color is connected to the new vertex, this vertex needs a new 4th color.Nevertheless, this 4 colored Graph can only be colored correctly, if the original 3 colored Graph is colored correctly. Therefor I reduced the 3 colore problem to a 4 color problem. Does this make sense? It would help me and others a lot if somebody could confirm my thoughts.

$\endgroup$ 6

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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