Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

Your question is about two decision problems. Let me start with stating these two problems explicitly. One is the usual 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.