3-colouring of a graph (polynomial time)?

Question

Can we colour a graph in 3 colours in polynomial time? I read that colouring a graph with 2
colours is easy,but colouring a graph with 3 different colours(No two vertices have the
same color) is np-hard.However,I wonder if there is a magic box that says 'yes' for 'A
graph being 3-colourable in polynomial time?'.If it says 'yes' how would it solve it in
polynomial time? Any Ideas ?

Answer 1

Add 3 new vertices to your graph called red/green/blue, each connected to the other 2 but nothing else.

Then for each vertex in your graph:

1. Connect the vertex to red and green if the resulting graph is 3 colourable
2. Otherwise, connect the vertex to green and blue if the resulting graph is 3 colourable
3. Otherwise, connect the vertex to red and blue (by construction the resulting graph must be 3 colourable)

At the end of this process you will have identified a colour for each vertex (the colour that it is not connected to).

This is O(N*magic) where magic is the complexity of your magic box.