# Reducing graph 3-coloring to 10-coloring

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?

• The bi-condition you took first is wrong as you yourself pointed out. For a (Turing) reduction from graph Problem A(here 3-coloring) to graph Problem B(here 10-coloring), all you need is to show that given a graph $G$, you can construct a graph $H$ such that $G$ is an yes instance of Problem A iff $H$ is an yes instance of Problem B. For most reductions, graph $H$ will not be same as graph $G$ – Cyriac Antony Apr 28 '19 at 3:56

3-coloring a graph is reducible to 10-coloring by a padding argument. Given a graph $G$ that you need to 3-color, create a new graph $H$ by adding the complete graph $K_7$ and making an edge from each of its vertices to all the vertices of $G$. The $K_7$ part of $H$ obviously cannot be colored with less than seven colors. None of those seven colors can be used in the coloring of the rest of $H$ because those vertices are adjacent to all the vertices of the $K_7$ part. So you can only 10-color $H$ if you can find a 3-coloring of the rest of $H$ with three new colors. The rest of $H$ is of course isomorphic to $G$ which means finding the 10-coloring for $H$ is just as hard as finding a 3-coloring for $G$.
This reduction can be done for any graph $G$ in polynomial time and therefore proves the NP-hardness of 10-coloring.