I am trying to show that the NP-Complete problem of 3-coloring a graph reduces to the problem of 10-coloring a graph.I have already shown how 10-coloring can be verified in polynomial time, and is thus in NP. Now I just need to show it indeed can be reduced to 3-coloring.
My thinking was to essentially prove a bi-conditional: given a graph G, we have that G has a 3-coloring iff G has a 10-coloring. Now, I am not sure how to go about showing this since, fairly obviously, G could have a 10-coloring and not a 3-coloring. So this leads me to believe that there must be some reduction that alters G in some way that lets me see that, yes, 3-coloring does reduce to 10-coloring. Problem is, I am having a difficult time visualizing this.
Can anyone help me out?