Find a 3-colouring using the 3-colourability decision problem
Let the vertices of the input graph&nbsp;$G$ be $\{v_1, \dots, v_n\}$.  First, check if $G$&nbsp;is 3-colourable: if not, output "No 3-colourings" and quit.

Otherwise, add new vertices called $r$, $g$ and&nbsp;$b$ to&nbsp;$G$ and add the edges $rb$, $bg$ and&nbsp;$br$. Call this graph $G_0$.  Note that $G_0$&nbsp;is 3-colourable and, in any 3-colouring of&nbsp;$G_0$, the three new vertices must receive different colours. Since the names of the colours are arbitrary, we will call the colour that $r$&nbsp;gets, red; call $g$&amp;'s colour, green; and call $b$'s colour blue.

We'll now create a sequence of graphs $G_1, \dots, G_n$, each of which will be 3-colourable, creating $G_i$ from $G_{i-1}$ as follows.


Set $G_i = G_{i-1} + \{rv_i, gv_i\}$ (i.e., the graph made by adding edges $rv_i$ and $gv_i$ to $G_{i-1}$) if this graph is is 3-colourable. Since $v_i$&nbsp;is adjacent to both $r$, which is red, and&nbsp;$g$, which is green, $v_i$ must be blue. 
Otherwise, set $G_i = G_{i-1} + \{gv_i, bv_i\}$, if this graph is 3-colourable. In this case, $v_i$ must be red.
Otherwise, set $G_i = G_{i-1} + \{bv_i, rv_i\}$.  Since $G_{i-1}$ was 3-colourable (you can prove this by induction), and we couldn't find a colouring with $v_i$ blue or red, $v_i$&nbsp;must be green.


The above procedure produces a 3-colouring of the $n$-vertex graph&nbsp;$G$ with $2n+1$ calls to the oracle (procedure) for checking 3-colourability.