2
$\begingroup$

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.

1 Answers 1

4

Your question is about two decision problems. Let me start with stating these two problems explicitly. One is the usual 3-colorability:

3-colorability
Instance: A graph G=(V,E).
Question: Is G 3-colorable?

and the other is the following problem. Because there is no standard name for the second problem, I just call it Problem X for the purpose of this answer.

Problem X
Instance: A graph G=(V,E).
Question: Is there an edge eE such that Ge is 3-colorable?

Suppose that we have the ability to solve Problem X and that we want to know whether a given graph G=(V,E) is 3-colorable or not. Let G′=G+K4 be the vertex-disjoint union of G and the complete graph on four vertices, and query the answer to Problem X on G′. It is not hard to prove that the answer to Problem X on G′ is yes if and only if G is 3-colorable; the proof is left as an exercise.

In complexity theory, what you are asking for is called a reduction from 3-colorability to Problem X.