# Polynomially reducing NP-Complete problem clarification

I am having trouble solving the following question.

I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable.

I want to show that $X \leq_p 3Col$

My attempt is to look at the complement of G, and say that the complement of G shows us that the graph plus the edge is not 3-colorable if and only if the G - e is 3-colorable.

Does this make sense and is it correct?

• Try to prove that your reduction works, and see for yourself. Mar 15 '16 at 21:09
• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Mar 16 '16 at 0:54

More interesting, perhaps, is a reduction going the other way, thus showing that X is NP-hard (and so NP-complete). Given a graph, we adjoin to it $K_4$, the clique on 4 vertices. The new graph is a Yes instance of X iff the original graph is 3-colorable (exercise).
Try removing each edge and checking if the remainder of the graph is 3-colorable. In this way you have shown that $X \leq E. 3Col$ in which $E$ is the number of edges and therefore polynomial.