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

Question

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.

I will appreciate to read your thoughts.

Answer 1

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.