# Algorithm for 3-coloring a graph, given a search algorithm that finds a k-colored graph for $k \ge 4$ if one exists, and otherwise returns false

The problem statement is:

Given a search algorithm that finds and returns a k-colored graph for $$k \ge 4$$ if one exists, and otherwise returns false, show that there exists a search algorithm for 3-coloring.

My idea is to connect each vertex $$v \in V$$ to another colored vertex(all new vertices are colored in the same color), and to use the given algorithm to find if there exists a 4-coloring for the new graph. If so, then the 3-coloring algorithm will return the colored graph that was returned from the 4-coloring algorithm, minus all the added vertices. If the 4-coloring algorithm fails, then the 3-coloring algorithm returns false.

I think the alogrithm works, as each node $$v \in V$$ can be colored only in one of three colors, since it is connected to a node which is already colored in a pre-defined color.

I've tried to build counter-examples to the algorithm, but I couldn't find any.

• "all new vertices are colored in the same color), and to use the given algorithm to find if there exists a 4-coloring for the new graph" In order to reduce 3-coloring to 4-coloring, just one new vertex should succeed. In general, you'd need $k-3$ new vertices. Commented Feb 13 at 23:04
Your idea works only if you are allowed to pre-color vertices. That's not given in the problem statement, so a much simpler idea is to add a single universal vertex, i.e. a vertex $$u$$ that is neighbors with every vertex in the graph. Let this graph be $$G'$$, and the original graph $$G = G' - u$$.
Now, if $$G'$$ is 4-colorable, then it assigns a color to $$u$$, $$\chi(u)$$ that no other vertex gets, hence $$G$$ is 3-colored. This holds both directions. Hence $$G$$ is 3-colorable if and only if $$G'$$ is 4-colorable. Indeed, something even stronger holds: $$G$$ is $$c$$-colorable if and only if $$G'$$ is $$c+1$$-colorable.