The question is rather explicit, but I will restate it here:
Given the ability to determine whether there is an edge that can be removed from a given graph to give a 3-colorable graph, how can I find whether any given graph is 3-colorable? (obviously we don't want a non-polynomial time algorithm)
Trying to add edges between all non-adjacent vertices of a the given graph G and repeatedly using the given ability won't work since the edge 'e' validating that G - e is 3-colorable might not have been added by our edge adding process.