3-Coloring Graph Turing Machine (Implementation Description)

Assume that G is an undirected graph.

1) Give an implementation description of a deterministic multi-tape Turing machine that decides the language B = { | G has a 3-coloring}.

2) Give an implementation description of a non-deterministic Truing machine that does not generate all possible ways to color the graph, and accepts the language B = { | G has a 3-coloring}.