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?
Best Answer
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.