Coloring Cyborgs

Problem:

Two cyborgs walk into your home, both claiming to be oracles for the graph 3-colorability decision problem. They both always give a yes/no answer in constant time for any instance, and are each self-consistent (i.e. each always gives the same answer for the same instance). However, one is a true oracle and the other is a shameless impostor, and you have a large instance of 3-colorability upon which they disagree. Prove whether it is possible to expose the impostor within time polynomial in the size of that instance.

Short Answer:

The key idea is to use the oracle (that only tell me yes or no) to output the coloring. The one that gives a valid coloring is the right one.

Proof:

We need a gadget for that, first, we add three nodes (call them red - green - blue ) as a triangle to the graph. If we wanted to force a node to be red, simply connect green and blue to it.

Now we have a mechanism to force a node to have a certain color - now we can guess the color of the nodes. Here is an algorithm to extract the 3 coloring from it.

For the cyborg that said the graph is 3 colourable, we run this algorithm:

while (there exists uncolored node)
{
  color it red
  if (the colored graph is not 3 colourable)
  {
    color it green instead
    if (the colored graph is not 3 colourable)
    {
      color it blue instead
      if (the coloured graph is not colourable)
      {
        output "you are fake oracle!";
      }
    }
  }
}
output you are true oracle!

The algorithm do at most 3 coloring attempt for each node, so it is obviously polynomial time!