Suppose we are given an oracle for the decision problem Is the given graph 3-colorable? (say we want to color every vertex either red, white, or blue). Given this oracle, we would like to actually find a 3-coloring.

In this problem you will design an algorithm that has the property that if the oracle runs in polynomial time, then your algorithm will run in polynomial time. Please provide the algorithm in python code format.

a) (Fixing a color) Design a way to force the oracle to color a specific vertex vV a given color. (Hint: consider adding a triangle, or 3-clique to the graph; assume WLOG that one node in the triangle is red, the other is white, and the last one is blue) b) (Search using the oracle) Give an algorithm that runs in a loop to compute the 3coloring. For this part, you can abstractly say statements like "add edges to the graph to fix a given vertex's color to be some given color" (the previous part supplies those details). (c) Briefly argue why your algorithm is correct, and runs in polynomial time assuming the oracle runs in polynomial time