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?